제출 #896051

#제출 시각아이디문제언어결과실행 시간메모리
896051alexander707070Copy and Paste 3 (JOI22_copypaste3)C++14
25 / 100
605 ms1116 KiB
#include<bits/stdc++.h>
#define MAXN 207
using namespace std;
 
const long long inf=1e15;
const long long mod=1000000000100011;
 
int n,len;
long long a,b,c,curr;
char s[MAXN];
 
long long dp[MAXN][MAXN];
bool li[MAXN][MAXN];
 
long long hesh(int l,int r){
    long long res=0;
    for(int i=l;i<=r;i++){
        res*=26; res+=s[i]-'a';
        res%=mod;
    }
    return res;
}

long long cost(long long len,long long cnt,long long sz){
    return (len-cnt*sz)*a+cnt*c;
}

void calc_dp(){
    for(int i=1;i<=n;i++){
        for(int f=1;f<=n;f++){
            dp[i][f]=inf;
        }
    }

    for(int len=1;len<=n;len++){
        for(int s=1;s+len-1<=n;s++){
            int l=s,r=s+len-1;

            if(len==1)dp[l][r]=a;

            dp[l-1][r]=min(dp[l-1][r],dp[l][r]+a);
            dp[l][r+1]=min(dp[l][r+1],dp[l][r]+a);

            long long cnt=0;

            for(int k=s;k<=n;k++){
                if(hesh(k,k+len-1)==hesh(l,r)){
                    cnt++;
                    dp[l][k+len-1]=min(dp[l][k+len-1],dp[l][r]+cost(k+len-1-l+1,cnt,r-l+1)+b );

                    k+=len-1;
                }
            }
        }
    }
}

 
int main(){
 
    cin>>n>>(s+1);
    cin>>a>>b>>c;

    calc_dp();
 
    cout<<dp[1][n]<<"\n";
 
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...