Chi Phí Biến Đổi Xâu
Points
40
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề 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$.
Community Discussion