Codeforces #667 : Div3. F. Subsequences of Length Two

本番は時間はすんなりだが１ミスがもったいない。
https://codeforces.com/contest/1409/problem/F

問題

２つの文字列S,Tと、整数Kが与えられる。
Sのうち最大K文字まで任意の文字列に変更できとき、Sの不連続でもよい部分文字列として、Tを最大何回登場させられるか。
なお、Tは２文字である。

解法

T[0]=T[1]の時は、SのうちT[0]と一致するものをとにかく増やせばよい。
それ以外の場合、
dp(n,m,k) := Sのうちn文字目まで見た場合、T[0]と一致するのがm文字で、k回文字変更を行ったとき、Tが部分文字列として現れる回数の最大値
としてDPしていけば、O(N^2×K)で求められる。

int N,K;
string S,T;

int from[202][202];
int to[202][202];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K>>S>>T;
	
	if(T[0]==T[1]) {
		x=0;
		FORR(c,S) if(c==T[0]) x++;
		x=min(N,x+K);
		cout<<x*(x-1)/2<<endl;
		return;
	}
	
	FOR(x,202) FOR(y,202) from[x][y]=-1<<30;
	from[0][K]=0;
	FOR(i,N) {
		FOR(x,202) FOR(y,202) to[x][y]=-1<<30;
		FOR(x,i+1) FOR(y,K+1) {
			to[x][y]=max(to[x][y],from[x][y]);
			if(S[i]==T[0]) to[x+1][y]=max(to[x+1][y],from[x][y]);
			if(y) to[x+1][y-1]=max(to[x+1][y-1],from[x][y]);
			if(S[i]==T[1]) to[x][y]=max(to[x][y],from[x][y]+x);
			if(y) to[x][y-1]=max(to[x][y-1],from[x][y]+x);
			
		}
		swap(from,to);
	}
	
	int ma=0;
	FOR(x,202) FOR(y,202) ma=max(ma,from[x][y]);
	cout<<ma<<endl;
	
	
	
}

まとめ

これは６問回にしては簡単な気がする。