結果
問題 |
No.291 黒い文字列
|
ユーザー |
![]() |
提出日時 | 2017-04-25 14:29:09 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 56 ms / 2,000 ms |
コード長 | 1,489 bytes |
コンパイル時間 | 1,659 ms |
コンパイル使用メモリ | 172,308 KB |
実行使用メモリ | 50,176 KB |
最終ジャッジ日時 | 2024-09-13 08:45:52 |
合計ジャッジ時間 | 3,133 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 26 |
ソースコード
#include<bits/stdc++.h> using namespace std; #define rep(i,a,b) for(int i=a;i<b;i++) string S; int dp[101][22][22][22][22]; //----------------------------------------------------------------------------------- int main() { cin >> S; dp[0][0][0][0][0] = 1; int n = S.length(); rep(i, 0, n) rep(K, 0, 21) rep(KU, 0, K + 1) rep(KUR, 0, KU + 1) rep(KURO, 0, KUR + 1) if(dp[i][K][KU][KUR][KURO]){ if (S[i] == 'K' || S[i] == '?') dp[i + 1][K + 1][KU][KUR][KURO] = max(dp[i + 1][K + 1][KU][KUR][KURO], dp[i][K][KU][KUR][KURO]); if (S[i] == 'U' || S[i] == '?') dp[i + 1][K][KU + 1][KUR][KURO] = max(dp[i + 1][K][KU + 1][KUR][KURO], dp[i][K][KU][KUR][KURO]); if (S[i] == 'R' || S[i] == '?') dp[i + 1][K][KU][KUR + 1][KURO] = max(dp[i + 1][K][KU][KUR + 1][KURO], dp[i][K][KU][KUR][KURO]); if (S[i] == 'O' || S[i] == '?') dp[i + 1][K][KU][KUR][KURO + 1] = max(dp[i + 1][K][KU][KUR][KURO + 1], dp[i][K][KU][KUR][KURO]); if (S[i] == 'I' || S[i] == '?') if(dp[i][K][KU][KUR][KURO] <= KURO) dp[i + 1][K][KU][KUR][KURO] = max(dp[i + 1][K][KU][KUR][KURO], dp[i][K][KU][KUR][KURO] + 1); dp[i + 1][K][KU][KUR][KURO] = max(dp[i + 1][K][KU][KUR][KURO], dp[i][K][KU][KUR][KURO]); } int ans = 0; rep(K, 0, 21) rep(KU, 0, K + 1) rep(KUR, 0, KU + 1) rep(KURO, 0, KUR + 1) ans = max(ans, dp[n][K][KU][KUR][KURO]); ans--; printf("%d\n", ans); }