//自信のない解法。左からgreedyにKUROIを作っていく. (TITECHとは違って左から作って大丈夫そう) //?を埋めるかどうか(各2通り)だけ全て試す。dp[何文字目か][次埋めるべき文字]でDPする。 //R?となっていたら、?にIを入れる意味はなくて、Oを入れるか否かで十分。 //左からgreedyがダメ(そりゃそうか)↓理由 //????UROIOI→KURKUROIOIのように、1112221122みたいになる奴(非広義単調増加)があって不味いのだ。 #include #include using namespace std; int dp[101][5]; int main() { static string s; static bool used[100] = {false}; cin >> s; for( int i = 0; i < 100; i++ ) for( int j = 0; j < 5; j++ ) dp[i][j] = -1919; dp[0][0] = 0; char *sub = "KUROI"; for( int i = 0; i < s.length(); i++ ){ for( int j = 0; j < 5; j++ ){ cout << dp[i][j] << " "; int nj = (j + 1) % 5; //使う if( s[i] == sub[j] || s[i] == '?' ) dp[i+1][nj] = max(dp[i+1][nj], dp[i][j] + (nj == 0)); //使わない dp[i+1][j] = max(dp[i+1][j], dp[i][j]); } cout << endl; } int ans = 0; for( int j = 0; j < 5; j++ ) ans = max(ans, dp[s.length()][j]); cout << ans << endl; return 0; }