SRM 558 div2 600 解き直し

スタンプの長さのとりうる値の範囲は
0[i-l+1, i]をスタンプで色j(それより前は何の色でもよい)で塗る, という条件で 塗る方法の数
というDPを思いついた。
あとは漸化式たてて解いて、最小となるLを見つけて計算する。
O(N^4)ぐらいだと思う

#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <algorithm>
#define REP(i, n) for(int i=0;i<n;i++)
using namespace std;

const int INF = 1 << 29;
class Stamp{
public:
	int N;
	string A;
	int getMinimumCost(string a, int sc, int pc){
		N = a.size();
		A = a;
		int ans = INF;
		for(int l=1; l <= N; l++){
			int t = c(l);
			if(t < INF)
				ans = min(ans, l * sc + pc * t);
		}
		return ans;
	}
	int c(int l){
		int dp[N+1][3];
		REP(i, N+1)REP(j, 3)
			dp[i][j] = INF;
		dp[0][0] = 0;
		dp[0][1] = 0;
		dp[0][2] = 0;
		for(int i=l; i<=N; i++){
			REP(j, 3){
				char col = (j==0)?'R':(j==1)?'G':'B';
				bool f = true;
				for(int k=i-l; k < i; k++){
					if(A[k] != '*' && A[k] != col){
						f = false;
						break;
					}
				}
				if(f){
					int m = INF;
					REP(k,3)
						m = min(m, dp[i-l][k]);
					for(int p = i-l; p < i; p++)
						m = min(m, dp[p][j]);
					dp[i][j] = (m >= INF) ? INF : m + 1;
				}
			}
		}
		return min(dp[N][0], min(dp[N][1], dp[N][2]));
	}
};