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 <algorithm>
#include <bitset>
#include <cstdint>
#include <cstring>
#include <iostream>
#include <limits.h>
#include <math.h>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define int long long
#define loop(X, N) for(int X = 0; X < (N); X++)
#define all(V) V.begin(), V.end()
#define rall(V) V.rbegin(), V.rend()
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef uint64_t u64;
typedef int64_t i64;
int n;
string s;
int A, B, C;
int maxCost;
vector<vvb> isEqualSubstring;
vvi substringCount;
map<pair<ii, ii>, int> memoize;
int solve(int a, int b, int c, int d) {
if (a == b) {
a = 0;
b = 0;
}
if (c == d) {
c = 0;
d = 0;
}
if (d - c == 0) return (b - a) * A;
if (memoize.count({{a, b}, {c, d}}))
return memoize[{{a, b}, {c, d}}];
/*
[a, b, c, d] depends on:
[a, x < b, c, d]
[0, 0, c, d] depends on:
[c, d, x < c, x <= y < d] && y - x < d - c
*/
int res = maxCost;
if (b - 1 >= a)
res = min(res, solve(a, b - 1, c, d) + A);
if (b - (d - c) >= a && d > c && isEqualSubstring[c][d][b - (d - c)]) {
res = min(res, solve(a, b - (d - c), c, d) + C);
}
if (a == 0 && b == 0) {
// loop(x, c) {
// for (int y = x; y < x + d - c; y++) { //y - x < d - c
// res = min(res, solve(c, d, x, y) + B);
// }
// }
for (int x = c; x <= d; x++) {
for (int y = x; y < d; y++) { //y - x < d - c
if (substringCount[x][y] <= 1 && y > x) continue;
res = min(res, solve(c, d, x, y) + B);
}
}
}
memoize[{{a, b}, {c, d}}] = res;
return res;
}
vector<vector<vvi>> dp;
int& get(int a, int b, int c, int d) {
if (a == b) {
a = 0;
b = 0;
}
if (c == d) {
c = 0;
d = 0;
}
return dp[a][b][c][d];
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
//dp cost of building S[a, b] with S[c, d] in clipboard
cin >> n;
cin >> s;
cin >> A >> B >> C;
maxCost = max({A, B, C}) * n;
isEqualSubstring = vector<vvb>(n + 1, vvb(n + 1, vb(n + 1)));
loop(i, n) {
loop(j, n) {
int sz = 1;
while (max(i, j) + sz <= n && s[i + sz - 1] == s[j + sz - 1]) {
isEqualSubstring[i][i + sz][j] = true;
sz++;
}
}
}
substringCount = vvi(n + 1, vi(n + 1));
loop(i, n + 1) {
for (int j = i + 1; j < n + 1; j++) {
int start = 0;
while (start < n) {
if (isEqualSubstring[i][j][start]) {
start += j - i;
substringCount[i][j]++;
}
else {
start++;
}
}
}
}
int result = maxCost;
loop(c, n + 1) {
for (int d = c; d < n + 1; d++) {
//result = min(result, dp[0][n][c][d]);
result = min(result, solve(0, n, c, d));
}
}
cout << result << endl;
/*
dp[a][b][c][d]
*/
// loop(i, n) {
// dp[i][i][n][n] = A;
// }
// for (int i = 1; i <= 2 * n; i++) {
// }
/*
dp[a][b][c][d]
dp[a][b][c][d] = min(dp[a][b][c][d], dp[a][b - 1][c][d] + A)
dp[0][0][c][d] = min(dp[c][d][a][b] + B)
if (s[b-(d-c), b] == s[c, d]) dp[a][b][c][d] = min(dp[a][b][c][d], dp[a][b-(d-c)][c][d] + C)
*/
// dp = vector<vector<vvi>>(n + 1, vector<vvi>(n + 1, vvi(n + 1, vi(n + 1, maxCost))));
// dp[0][0][0][0] = 0;
// loop(c, n + 1) {
// for (int d = c; d < n + 1; d++) {
// loop(a, n + 1) {
// for (int b = a; b < n + 1; b++) {
// /*
// [a, b, c, d] depends on:
// [a, x < b, c, d]
// [0, 0, a, b] depends on:
// [a, b, c, y <= b]
// */
// if (b - 1 >= a)
// get(a, b, c, d) = min(get(a, b, c, d), get(a, b - 1, c, d) + A);
// if (b - (d - c) >= a && d > c && s.substr(b - (d - c), d - c) == s.substr(c, d - c)) {
// get(a, b, c, d) = min(get(a, b, c, d), get(a, b - (d - c), c, d) + C);
// }
// if (d <= b)
// get(0, 0, a, b) = min(get(0, 0, a, b), get(a, b, c, d) + B);
// }
// }
// }
// }
return 0;
// vvi cost(n + 1, vi(n + 1, maxCost));
// cost[0][0] = 0;
// //cost[0][j] = min(cost[j][i] + B)
// //cost[i][j] = min(cost[i - j][j] + C, cost[i - 1][j] + A)
// loop(i, n + 1) {
// loop(j, n + 1) {
// if (i - 1 >= 0) cost[i][j] = min(cost[i][j], cost[i - 1][j] + A);
// if (i - j >= 0) cost[i][j] = min(cost[i][j], cost[i - j][j] + C);
// cost[0][i] = min(cost[0][i], cost[i][j] + B);
// }
// }
// int result = maxCost;
// loop(j, n + 1) {
// result = min(result, cost[n][j]);
// }
// cout << result << endl;
// 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... |