#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2500 + 2,MOD = (int)1e9 + 7;
struct H{
int p,mod;
vector<ll> h,inv;
ll binpow(ll a,ll b) {
ll ret = 1,k = a;
while(b) {
if(b & 1) {
ret *= k;
ret %= mod;
}
k *= k;
k%=mod;
b /= 2;
}
return ret;
}
void init(string s) {
int n = (int)s.size();
h.resize((int)s.size());
inv.resize((int)s.size());
ll x = 1;
for(int i = 0;i < n;i++) {
h[i] = x * 1ll * (s[i] - 'a' + 1)%mod;
if(i) h[i] += h[i - 1];
if(h[i] >= mod) h[i] -= mod;
inv[i] = binpow(x,mod-2);
x = x * 1ll * p%mod;
}
}
int get(int l,int r) {
ll val = h[r];
if(l) {
val -= h[l - 1];
}
if(val < 0) val += mod;
val = val * inv[l]%mod;
return val;
}
}xx,yy;
string s;
ll a,b,c;
int n;
ll dp[N][N];
int nx[N][N];
map<pair<int,int>,vector<pair<int,int>>> f;
vector<array<int,3>> x;
void test() {
cin >> n >> s >> a >> b >> c;
yy.p = 37;yy.mod = 998244353;yy.init(s);
xx.p = 167;xx.mod = (int)1e9 + 7;xx.init(s);
bool sub = true;
for(int i = 0;i < n;i++) {
if(s[i] != 'a') {
sub = false;
}
}
ll res = n * 1ll * a;
for(int i = 0;i < n;i++) {
for(int j = i;j < n;j++) {
int ff = xx.get(i,j),tt = yy.get(i,j);
ll val = (ff * 1ll * tt % MOD + ff + tt + (f ^ t))%MOD;
f[{val,0}].push_back({i,j});
}
}
for(int l = 0;l < n;l++) {
for(int r = 0;r < n;r++) {
dp[l][r] = 1e18;
}
}
for(auto [t,k]:f) {
int it = (int)k.size() - 1;
for(int j = (int)k.size() - 1;j >= 0;j--) {
while(it >= 0 && k[it].first > k[j].second) {
it--;
}
if(it == (int)k.size() - 1) {
nx[k[j].first][k[j].second] = -1;
} else {
nx[k[j].first][k[j].second] = k[it + 1].first;
}
}
}
for(int l = 0;l < n;l++) {
dp[l][l] = a;
for(int r = l;r < n;r++) {
x.push_back({r - l + 1,l,r});
}
}
sort(x.begin(),x.end());
for(auto [s,l,r]:x) {
dp[l][r] = min({dp[l][r],dp[l + 1][r] + a,dp[l][r - 1] + a});
int l_ = l,r_ = r;
int occ = 1;
int len = (r - l + 1);
// cout << l << ' ' << r << ' ' << dp[l][r] << '\n';
while(l_ != -1) {
int sz = (r_ - l + 1);
ll val = (sz - occ * 1ll * len) * 1ll * a + b + occ * c + dp[l][r];
dp[l][r_] = min(dp[l][r_],val);
occ++;
l_ = nx[l_][r_];
r_ = l_ + len - 1;
}
}
cout << dp[0][n-1] << '\n';
}
signed main() {
ios_base::sync_with_stdio(false);cin.tie(0);
int t = 1;
// cin >> t;
while(t--) {
test();
}
}
Compilation message
copypaste3.cpp: In function 'void test()':
copypaste3.cpp:68:60: error: 't' was not declared in this scope; did you mean 'tt'?
68 | ll val = (ff * 1ll * tt % MOD + ff + tt + (f ^ t))%MOD;
| ^
| tt
copypaste3.cpp:64:8: warning: unused variable 'res' [-Wunused-variable]
64 | ll res = n * 1ll * a;
| ^~~
