KUPC2015 : A - 東京都

うーん、詰めが甘くて解けそうな問題を解ききれず微妙な順位。
http://kupc2015.contest.atcoder.jp/tasks/kupc2015_a

問題

文字列Sが与えられる。
ここから連続した部分列として"tokyo"または"kyoto"を最大何個とれるか。

解法

典型的なDP問題。
先頭から文字列を見ていって、dp[最後の文字] := (tokyoまたはkyotoの最大登場回数)とする。
ラスト５文字がtokyoかkyotoなら、dp[最後の文字] = max(dp[最後の文字-1], dp[最後の文字-5]+1)として値を更新していけばよい。

int T;
int dp[1010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>s;
		FOR(i,s.size()) {
			dp[i+1]=dp[i];
			if(i>=4) if(s.substr(i-4,5)=="tokyo" || s.substr(i-4,5)=="kyoto") {
				dp[i+1]=max(dp[i+1],dp[i+1-5]+1);
			}
		}
		cout<<dp[s.size()]<<endl;
	}
	
}

まとめ

まだ簡単。