SRM 558 div2 600 解き直し
スタンプの長さのとりうる値の範囲は
0
という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])); } };