This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
char s[2505];
int qs[2505][2505];
ll dp[2505][2505];
ll A, B, C;
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n;
cin >> n;
bool ch = 1;
for (int i = 1;i <= n;i++) {
cin >> s[i];
ch &= s[i] == 'a';
}
cin >> A >> B >> C;
if (ch) {
vector<ll> dp(n + 2, 0);
for (int i = 1;i <= n;i++) {
dp[i] = dp[i - 1] + A;
for (int j = 1;j < i;j++) {
dp[i] = min(dp[i], (dp[j] + B) + A * (i % j) + C * (i / j));
}
}
cout << dp[n] << '\n';
return 0;
}
for (int i = 1;i <= n;i++) {
for (int j = 1;i + j <= n;j++) {
qs[i][j] = s[i] == s[i + j];
}
for (int j = 1;j <= n;j++) {
qs[i][j] += qs[i - 1][j];
}
}
for (int i = 1;i <= n;i++) {
for (int j = i + 1;j <= n;j++) {
dp[i][j] = (j - i + 1) * A;
}
}
for (int i = 1;i <= n;i++) {
dp[i][i] = A;
int cnt = 1;
for (int j = i + 1;j <= n;j++) {
if (s[i] == s[j]) {
cnt++;
dp[i][j] = min(dp[i][j], A * (j - i + 1 - cnt) + A + B + cnt * C);
}
}
}
for (int k = 1;k < n;k++) {
for (int i = 1;i <= n - k;i++) {
int j = i + k;
dp[i][j] = min(dp[i][j], A + dp[i + 1][j]);
dp[i][j] = min(dp[i][j], dp[i][j - 1] + A);
int cnt = 1, prev = j;
for (int l = j + k + 1;l <= n;l++) {
int x = l - j;
if (qs[j][x] - qs[i - 1][x] == j - i + 1) {
if (l - prev > k) {
cnt++;
prev = l;
}
dp[i][l] = min(dp[i][l], A * (l - i + 1 - cnt * (k + 1)) + (dp[i][j] + B) + cnt * C);
}
}
}
}
cout << dp[1][n] << '\n';
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |