#include <bits/stdc++.h>
// sol: y tuong: voi moi doan l r, neu ta paste no, ta se di thang den doan l r dang sau, con lai dung A
typedef long long ll;
#define endl '\n'
#define yes //cout<<"YES"<<endl;
#define no //cout<<"NO"<<endl;
#define fi first
#define se second
#define pii pair<ll, ll>
#define inf 1e18
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);//cout.tie(NULL);
#define MP make_pair
#define TASK "ghuy4g"
#define start if(fopen(TASK".inp","r")){freopen(TASK".inp","r",stdin);freopen(TASK".out","w",stdout);}
#define LOG 19
#define N 2502
using namespace std;
bool ghuy4g;
const ll base = 311;
const ll mod1 = 1000000007;
const ll mod2 = 1000000009;
int n, A, B, C, nxt[N][N];
long long dp[2502][2502];
string s;
long long p1[N], p2[N], h1[N], h2[N];
vector<ll> vt[N][N];
unordered_map<ll, ll> mp[N];
ll cur[N];
void build() {
p1[0] = p2[0] = 1;
h1[0] = h2[0] = 0;
for (int i = 1; i <= n; i ++) {
h1[i] = (h1[i - 1] * base % mod1 + (s[i] - 'a')) % mod1;
h2[i] = (h2[i - 1] * base % mod2 + (s[i] - 'a')) % mod2;
p1[i] = p1[i - 1] * base % mod1;
p2[i] = p2[i - 1] * base % mod2;
}
}
ll get(ll l, ll r) {
ll x1 = (h1[r] - h1[l - 1] * p1[r - l + 1] % mod1 + mod1) % mod1;
ll x2 = (h2[r] - h2[l - 1] * p2[r - l + 1] % mod2 + mod2) % mod2;
return (x1 << 32) ^ x2;
}
void pre() {
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= n; j ++) {
dp[i][j] = inf;
}
dp[i][i] = A;
}
for (int i = 1; i <= n; i ++) {
for (int j = i; j <= n; j ++) {
ll x = get(i, j);
if (mp[j - i + 1][x] == 0) {
mp[j - i + 1][x] = ++ cur[j - i + 1];
}
vt[j - i + 1][mp[j - i + 1][x]].push_back(i);
}
}
for (int len = 1; len <= n; len ++) {
for (int id = 1; id <= cur[len]; id ++) {
sort(vt[len][id].begin(), vt[len][id].end());
ll it = vt[len][id].size() - 1;
if (vt[len][id].size() == 0) continue;
for (int j = vt[len][id].size() - 1; j >= 0; j --) {
while (it > 0 && vt[len][id][it - 1] - vt[len][id][j] >= len) {
it -- ;
}
if (it >= 0 && vt[len][id][it] - vt[len][id][j] >= len) {
nxt[len][vt[len][id][j]] = vt[len][id][it];
}
}
}
}
}
void solve() {
for (int len = 1; len <= n; len ++) {
for (int i = 1; i <= n - len + 1; i ++) {
ll j = i + len - 1;
dp[i][j] = min({dp[i][j], dp[i][j - 1] + A, dp[i + 1][j] + A});
ll cnt = 1, z = nxt[j - i + 1][i];
while (z) {
++ cnt;
dp[i][z + len - 1] = min(dp[i][z + len - 1], dp[i][j] + B + C * cnt + (z + len - 1 - i + 1 - cnt * len) * A );
z = nxt[j - i + 1][z];
}
}
}
cout << dp[1][n];
}
bool klinh;
signed main(void) {
faster;
cin >> n >> s >> A >> B >> C;
s = '*' + s;
build();
pre();
solve();
cerr << fabs(&klinh - &ghuy4g) / 1048576.0;
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... |