SRM558 Div1 Easy - Stamp

問題

長さnの無色のセルの列があり、左からi番目のセルはs[i]色で塗りたい
何色で塗ってもいいセルもある
このために、まず好きなサイズのスタンプを1つ選ぶ
サイズLのスタンプを使うにはst*Lだけコストがかかる
またスタンプを押す度にpsだけコストがかかる
一度色を塗ったセルを違う色で上書きすることはできない
(同じ色で同じセルを2回以上押すのはok)
希望通りに全てのセルを塗るための最小コストを求めよ

1 <= n <= 50
1 <= st, ps <= 10^5

解法

スタンプのサイズLを全部試す
dp[i][j]: 最後に押した色がjで、左からi番目までを希望通りに塗ったときの最小コスト
dp[i]からはs[l,r)が全て同じ色(または'*')のときのみdp[r]に遷移する
サンプル3みたいに、スタンプの左端をiより左に合わせて押さないといけないこともあることに注意
そういう場合は範囲の色が同じって条件に加えて最後に使った色と今塗ろうとしてる色が一致する必要もある

class Stamp {
public:
	int getMinimumCost(string s, int st, int ps) {
		int n = s.size(), dp[55][3], res = 1<<30;
		map<char,int> con = {{'R',0}, {'G',1}, {'B',2}};
		reps(len,1,n+1) {
			rep(i,55) rep(j,3) dp[i][j] = 1<<30;
			dp[0][0] = 0;
			rep(i,n) rep(j,3) reps(k,1,len+1) rep(c,3) {
				int r = i+k, l = r-len, ng = 0; // [l,r)
				if (l<0 || n<r) continue;
				reps(x,l,r) if (s[x]!='*' && con[s[x]]!=c) ng = 1;
				if (l<i && j!=c) ng = 1;
				if (!ng) chmin(dp[r][c], dp[i][j] + ps);
			}
			chmin(res, len*st + *min_element(dp[n], dp[n]+3));
		}
		return res;
	}
};

https://community.topcoder.com/stat?c=problem_statement&pm=11835&rd=15180