Chi Phí Biến Đổi Xâu

Buổi 65-66 — Mock HSG Dynamic Programming dynamic-programming
Points
40
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề bài

Cho hai xâu $A$ và $B$ gồm các chữ cái tiếng Anh in thường. Bạn có thể biến đổi $A$ thành $B$ bằng ba phép toán:

  • Chèn một ký tự bất kỳ vào $A$ với chi phí $C_{ins}$.
  • Xóa một ký tự bất kỳ khỏi $A$ với chi phí $C_{del}$.
  • Thay thế một ký tự trong $A$ 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 $A$ thành $B$.
Dữ liệu vào
  • Dòng đầu chứa xâu $A$.
  • Dòng thứ hai chứa xâu $B$.
  • Dòng thứ ba chứa ba số nguyên $C_{ins}, C_{del}, C_{rep}$.
Dữ liệu ra

Một số nguyên duy nhất là tổng chi phí nhỏ nhất.

Ví dụ
Input Output
kitten
sitting
1 1 2
5
Giới hạn
  • $1 \le |A|, |B| \le 1000$.
  • $1 \le C_{ins}, C_{del}, C_{rep} \le 10^4$.
Draft saved