この回BがC,Dより正答者少ないんだな。
https://codeforces.com/contest/1120/problem/C
問題
文字列Sが与えられる。
これを複数の部分文字列T[i]の連結として表したい。
その際、Tは以下のいずれかを満たす形でなければならず、その際下記のコストがかかる。
- |T[i]|=1ならコストA
- T[i]がT[1]~T[i-1]を連結した文字列の部分文字列に一致する場合、コストB
Sを構成する際の最小コストはいくつか。
解法
SのprefixがS'=T[1]~T[i-1]の連結であるとき、S'+T[i]を構成するときの最小コストを考える。
前者のケースは明らかなので、後者のケースはT[i]として最長何文字を取れるか事前にチェックしよう。
そうすればあとはT[i]が何文字とるかを総当たりしながら最小コストをDPするだけ。
int same[5050][5050]; int mal[5050]; int N,A,B; string S; ll dp[5050]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>A>>B>>S; for(i=1;i<N;i++) { x=N-1-i; same[x][x+i]=S[x]==S[x+i]; for(x=N-2-i;x>=0;x--) { if(S[x]==S[x+i]) same[x][x+i]=1+same[x+1][x+1+i]; } } FOR(y,N) { FOR(x,y) mal[y]=max(mal[y],min(same[x][y],y-x)); } FOR(x,5050) dp[x]=1LL<<60; dp[0]=0; FOR(i,N) { dp[i+1]=min(dp[i+1],dp[i]+A); for(j=1;j<=mal[i];j++) dp[i+j]=min(dp[i+j],dp[i]+B); } cout<<dp[N]<<endl; }
まとめ
Bより明らかに簡単でない?