Chi phí biến đổi

Xem PDF

Nộp bài


Điểm: 15 (thành phần)
Thời gian: 1.0s
Bộ nhớ: 512M

Tác giả:
Dạng bài

Cho xâu \(S\) độ dài \(N\) chỉ chứa các ký tự latin in thường. Ta ký hiệu \(S_i\) \((1\le i\le N)\) là ký tự thứ \(i\) từ trái sang của xâu \(S\).

Bạn được phép thực hiện hai phép biến đổi sau lên \(S\) với một số lượng lần tùy ý:

  • Bỏ ra \(A\) đồng để đưa ký tự đầu tiên bên trái của \(S\) sang tận cùng bên phải. Nói cách khác, sau khi áp dụng phép biến đổi này thì xâu \(\overline{S_1S_2S_3...S_N}\) sẽ trở thành \(\overline{S_2S_3...S_NS_1}\).
  • Bỏ ra \(B\) đồng để gán \(S_i\) \((1\le i\le N)\) thành một ký tự latin in thường bất kỳ.

Cho biết các giá trị \(N\), \(A\), \(B\) và xâu \(S\) ở trạng thái ban đầu, hãy tìm cách biến đổi với chi phí thấp nhất để biến \(S\) trở thành một xâu đối xứng.

Ghi chú: Một xâu ký tự \(T\) được xem là xâu đối xứng nếu ta đọc nó từ trái qua phải cũng y hệt như đọc từ phải qua trái. Nói cách khác, nếu xâu \(T=\overline{T_1T_2...T_L}\) có \(T_1=T_L\), \(T_2=T_{L-1}\), \(T_3=T_{L-2}\),... thì nó là một xâu đối xứng.

Input
  • Dòng đầu chứa ba số nguyên dương \(N\), \(A\), \(B\) \(\left(1\le N\le 5000, 1\le A,B\le 10^9\right)\).
  • Dòng tiếp theo chứa xâu \(S\) độ dài \(N\) chỉ gồm các chữ cái latin in thường.
Output
  • In ra chi phí nhỏ nhất để biến đổi \(S\) thành một xâu đối xứng.
Ví dụ
Sample input 01
5 1 2
aatvb
Sample output 01
3
Giải thích

Cách biến đổi tối ưu nhất sẽ tốn \(3\) đồng:

  • Đầu tiên, bỏ ra \(2\) đồng để gán \(S_5=\)t. Sau đó, \(S=\)aatvt.
  • Tiếp theo, bỏ ra \(1\) đồng để dịch chuyển \(S_1\) về cuối sau. Sau đó, \(S=\)atvta là một xâu đối xứng.