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;
typedef long long ll;
const int MX=2505;
int N, A, B, C;
string s;
ll dp[MX][MX];
ll ndp[MX];
const int P=1e9+93, mod=2'147'483'647;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll hsh[MX][MX], pw[MX], key[MX];
bool ok(int a, int b, int l, int r) {
if(l<=b) return false;
return hsh[a][b]==hsh[l][r];
}
int main() {
cin.tie(0); ios_base::sync_with_stdio(0);
for(int i=0;i<MX;i++)
for(int j=i;j<MX;j++)
dp[i][j]=2e18;
pw[0]=1;
for(int i=1;i<MX;i++) pw[i]=pw[i-1]*P%mod;
cin>>N;
cin>>s;
cin>>A>>B>>C;
s='#'+s;
for(int c=0;c<26;c++) key[c]=rng()%mod;
for(int l=1;l<=N;l++) {
for(int r=l;r<=N;r++) {
int p=r-l+1;
hsh[l][r]=hsh[l][r-1]+pw[p]*(key[s[r]-'a'])%mod;
hsh[l][r]%=mod;
}
}
for(int l=N;l>0;l--) {
for(int r=l;r<=N;r++) {
dp[l][r]=min(dp[l][r],dp[l][r-1]+A);
for(int k=r;k<=N;k++) ndp[k]=2e18;
int len=r-l+1;
ndp[r]=min(dp[l][r]+B+C,dp[l][r]+B+dp[l][r]);
for(int k=r+1;k<=N;k++) {
if(ok(l,r,k-len+1,k)) ndp[k]=min(ndp[k],ndp[k-len]+C);
ndp[k]=min(ndp[k],ndp[k-1]+A);
}
for(int k=r+1;k<=N;k++) {
dp[l][k]=min(dp[l][k],ndp[k]);
}
dp[l-1][r]=min(dp[l-1][r],dp[l][r]+A);
}
}
cout<<dp[1][N]<<'\n';
}
# | 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... |