| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P172SUME - ROUND 2E - Bài học đáng nhớ |
Dĩn và Lúi chơi rất thân với nhau nhưng Dĩn lại rất hay phán xét về nhan sắc của Lúi. Do quá cay cú nên hôm nay Lúi quyết định sẽ dạy cho Dĩn một bài học :v. Với khối kiến thức khủng lồ của mình Lúi đã nghĩ ra một bài học mà chắc chắc Dĩn sẽ sml. Lúi yêu cầu Dĩn đếm thời gian tối thiểu để có thể ghép được 1 xâu cho trước, ban đầu xâu có độ dài bằng 0. Có 2 cách để ghép xâu:
-Thêm 1 kí tự vào cuối xâu sẽ mất A(s).
-Tìm 1 xâu con của xâu vừa được tạo trước đó, thêm xâu con vào cuối xâu sẽ mất B(s).
Nếu Dĩn không làm được thì Lúi sẽ rất thỏa mãn nên bạn hãy giúp Dĩn để Lúi không đạt đuọc mục đích của mình nhé =)))
Input
Dòng đầu là số bộ test T (T<=3)
Mỗi bộ test gồm:
Dòng đầu là 3 số n,A,B. , n là độ dài của xâu cần ghép
1<=n<=30000, 1<=A,B<=10000.
Dòng tiếp theo là xâu cần ghép.Xâu chỉ bao gồm các kí tự từ ‘a’ -> ‘z’.
Output
Mỗi dòng là kết quả của mỗi bộ test.
Example
Input: 1
9 8 9
bacbacacb Output: 42
Giải thích:
Ban đầu S=””;
Thêm kí tự ‘b’ -> S=”b”, mất 8s
Thêm kí tự ‘a’ -> S=”ba”, mất 8s
Thêm kí tự ‘c’ -> S=”bac”, mất 8s
Thêm xâu con “bac” -> S=”bacbac”, mất 9s
Thêm xâu con “acb” -> S=”bacbacacb”, mất 9s
Tổng thời gian sẽ là 8+8+8+9+9= 42s.
| Được gửi lên bởi: | adm |
| Ngày: | 2017-07-21 |
| Thời gian chạy: | 1s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 ASM64 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
