結果
問題 |
No.291 黒い文字列
|
ユーザー |
![]() |
提出日時 | 2015-10-17 08:39:50 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 17 ms / 2,000 ms |
コード長 | 1,647 bytes |
コンパイル時間 | 829 ms |
コンパイル使用メモリ | 96,936 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-22 07:52:44 |
合計ジャッジ時間 | 1,895 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 26 |
ソースコード
#include <iostream> #include <algorithm> #include <cmath> #include <vector> #include <complex> #include <queue> #include <deque> #include <set> #include <map> #include <unordered_set> #include <unordered_map> #include <iomanip> #include <assert.h> #include <array> #include <cstdio> #include <cstring> using namespace std; #define REP(i,a,b) for(int i=a;i<(int)b;i++) #define rep(i,n) REP(i,0,n) typedef long long ll; #define chmax(a,x) a=max(a,x) int dp[2][21][21][21][21]; int main() { string s; cin >> s; int N = s.size(); memset(dp[0], -1, sizeof dp[0]); dp[0][0][0][0][0] = 0; rep(idx, N) { memset(dp[(idx+1)&1], -1, sizeof dp[(idx+1)&1]); rep(k, 21) rep(u, k+1) rep(r, u+1) rep(o, r+1) { if(dp[idx&1][k][u][r][o] < 0) { continue; } dp[(idx+1)&1][k][u][r][o] = max(dp[(idx+1)&1][k][u][r][o], dp[idx&1][k][u][r][o]); if(s[idx] == 'K' || s[idx] == '?') { chmax(dp[(idx+1)&1][min(20,k+1)][u][r][o], dp[idx&1][k][u][r][o]); } if(s[idx] == 'U' || s[idx] == '?') { chmax(dp[(idx+1)&1][k][min(20,u+1)][r][o], dp[idx&1][k][u][r][o]); } if(s[idx] == 'R' || s[idx] == '?') { chmax(dp[(idx+1)&1][k][u][min(20,r+1)][o], dp[idx&1][k][u][r][o]); } if(s[idx] == 'O' || s[idx] == '?') { chmax(dp[(idx+1)&1][k][u][r][min(20,o+1)], dp[idx&1][k][u][r][o]); } if(s[idx] == 'I' || s[idx] == '?') { if(o) chmax(dp[(idx+1)&1][k-1][u-1][r-1][o-1], dp[idx&1][k][u][r][o] + 1); } } } int ans = 0; rep(k,21)rep(u,21)rep(r,21)rep(o,21){ ans = max(ans, dp[N&1][k][u][r][o]); } cout << ans << endl; return 0; }