結果
問題 |
No.291 黒い文字列
|
ユーザー |
![]() |
提出日時 | 2015-10-17 05:58:01 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 57 ms / 2,000 ms |
コード長 | 2,268 bytes |
コンパイル時間 | 948 ms |
コンパイル使用メモリ | 92,176 KB |
実行使用メモリ | 26,624 KB |
最終ジャッジ日時 | 2024-07-22 07:49:39 |
合計ジャッジ時間 | 2,471 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 26 |
ソースコード
#include <iostream> #include <vector> #include <cstdio> #include <sstream> #include <map> #include <string> #include <algorithm> #include <queue> #include <cmath> #include <set> using namespace std; //resize(vector, {v1,v2,v3}); void resize(int& val , vector<int>::iterator itr){val = 0;} void resize(long long& val , vector<int>::iterator itr){val = 0;} void resize(double& val , vector<int>::iterator itr){val = 0;} template<class T> void resize(vector<T>& vec, vector<int>::iterator itr){ vec.resize(*itr); for(int i=0; i<*itr; i++){ resize(vec[i], itr+1); } } template<class T> void resize(T& vec, vector<int> sz){ resize(vec, sz.begin()); } int main(){ string s; cin >> s; int n = s.size(); int m = n/5; vector<vector<vector<vector<vector<int>>>>> dp; resize(dp, {m+1,m+1,m+1,m+1,m+1}); string kuroi = "KUROI?"; int check = 0; for(int i=0; i<5; i++){ check |= 1<<(kuroi[i]-'A'); } check = ~check; dp[0][0][0][0][0] = 1; for(int x=0; x<n; x++){ if(s[x] != '?') if( check & (1<<(s[x]-'A') )){ continue; } /* vector<vector<vector<vector<vector<int>>>>> dp_; resize(dp_, {m+1,m+1,m+1,m+1,m+1}); for(int k=0; k<=m; k++) for(int u=0; u<=k; u++) for(int r=0; r<=u; r++) for(int o=0; o<=r; o++) for(int i=0; i<=o; i++){ */ for(int k=m; k>=0; k--) for(int u=k; u>=0; u--) for(int r=u; r>=0; r--) for(int o=r; o>=0; o--) for(int i=o; i>=0; i--){ int& pos = dp[k][u][r][o][i]; if(pos==0) continue; pos = 0; if(s[x] == '?'){ dp[min(m,k+1)][u][r][o][i] = 1; dp[k][min(k,u+1)][r][o][i] = 1; dp[k][u][min(u,r+1)][o][i] = 1; dp[k][u][r][min(r,o+1)][i] = 1; dp[k][u][r][o][min(o,i+1)] = 1; }else if(s[x]=='K'){ dp[min(m,k+1)][u][r][o][i] = 1; }else if(s[x] == 'U'){ dp[k][min(k,u+1)][r][o][i] = 1; }else if(s[x] == 'R'){ dp[k][u][min(u,r+1)][o][i] = 1; }else if(s[x] == 'O'){ dp[k][u][r][min(r,o+1)][i] = 1; }else if(s[x] == 'I'){ dp[k][u][r][o][min(o,i+1)] = 1; } } //swap(dp, dp_); } int ans = 0; for(int k=0; k<=m; k++) for(int u=0; u<=k; u++) for(int r=0; r<=u; r++) for(int o=0; o<=r; o++) for(int i=0; i<=o; i++){ int& pos = dp[k][u][r][o][i]; if(pos==0) continue; ans = max(ans, i); } cout << ans << endl; return 0; }