Codeforces #543 Div1 C. Compress String

この回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より明らかに簡単でない？