Biến đổi xâu với chi phí tối thiểu

Buổi 22 — DP 2D & LIS Dynamic Programming
Points
40
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Submissions
Đề bài

Cho hai xâu ký tự $S$ và $T$ chỉ gồm các chữ cái tiếng Anh viết thường. Bạn có thể biến đổi xâu $S$ thành xâu $T$ bằng ba phép toán sau:

  • Chèn một ký tự bất kỳ vào vị trí bất kỳ với chi phí $C_{ins}$.
  • Xóa một ký tự bất kỳ trong xâu với chi phí $C_{del}$.
  • Thay thế một ký tự bằng một ký tự khác với chi phí $C_{rep}$.

Hãy tìm tổng chi phí nhỏ nhất để biến đổi xâu $S$ thành xâu $T$.

Dữ liệu vào
  • Dòng đầu tiên chứa ba số nguyên $C_{ins}, C_{del}, C_{rep}$ ($1 \le C_{ins}, C_{del}, C_{rep} \le 10^6$).
  • Dòng thứ hai chứa xâu $S$ ($1 \le |S| \le 1000$).
  • Dòng thứ ba chứa xâu $T$ ($1 \le |T| \le 1000$).
Dữ liệu ra
  • In ra một số nguyên duy nhất là tổng chi phí nhỏ nhất.
Ví dụ
Input Output
2 3 4
kitten
sitting
10
Giới hạn
  • $1 \le |S|, |T| \le 1000$
  • $1 \le C_{ins}, C_{del}, C_{rep} \le 10^6$
Draft saved