結果
問題 |
No.291 黒い文字列
|
ユーザー |
![]() |
提出日時 | 2016-04-01 19:35:44 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 14 ms / 2,000 ms |
コード長 | 2,553 bytes |
コンパイル時間 | 760 ms |
コンパイル使用メモリ | 89,388 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2024-10-02 08:51:52 |
合計ジャッジ時間 | 1,920 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 26 |
ソースコード
/* -*- coding: utf-8 -*- * * 291.cc: No.291 黒い文字列 - yukicoder */ #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #include<string> #include<vector> #include<map> #include<set> #include<stack> #include<list> #include<queue> #include<deque> #include<algorithm> #include<numeric> #include<utility> #include<complex> #include<functional> using namespace std; /* constant */ const int MAX_N = 100; const int MAX_M = MAX_N / 5; /* typedef */ typedef vector<int> vi; /* global variables */ vi as; int dp[2][MAX_M + 1][MAX_M + 1][MAX_M + 1][MAX_M + 1]; /* subroutines */ /* main */ int main() { string s; cin >> s; for (int i = 0; i < s.size(); i++) switch (s[i]) { case 'K': as.push_back(1 << 0); break; case 'U': as.push_back(1 << 1); break; case 'R': as.push_back(1 << 2); break; case 'O': as.push_back(1 << 3); break; case 'I': as.push_back(1 << 4); break; case '?': as.push_back((1 << 5) - 1); break; } int n = as.size(); int m = n / 5; //for (int i = 0; i < n; i++) printf("%d ", as[i]); putchar('\n'); memset(dp[0], -1, sizeof(dp[0])); dp[0][0][0][0][0] = 0; int cur = 0, nxt = 1; for (int i = 0; i < n; i++) { int &ai = as[i]; memcpy(dp[nxt], dp[cur], sizeof(dp[nxt])); 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++) { int &dpc = dp[cur][k][u][r][o]; if (dpc >= 0) { //printf("dp[%d][%d][%d][%d]=%d\n", k, u, r, o, dpc); if (ai & (1 << 0)) { int k0 = min(m, k + 1); if (dp[nxt][k0][u][r][o] < dpc) dp[nxt][k0][u][r][o] = dpc; } if (ai & (1 << 1)) { int u0 = min(k, u + 1); if (dp[nxt][k][u0][r][o] < dpc) dp[nxt][k][u0][r][o] = dpc; } if (ai & (1 << 2)) { int r0 = min(u, r + 1); if (dp[nxt][k][u][r0][o] < dpc) dp[nxt][k][u][r0][o] = dpc; } if (ai & (1 << 3)) { int o0 = min(r, o + 1); if (dp[nxt][k][u][r][o0] < dpc) dp[nxt][k][u][r][o0] = dpc; } if (ai & (1 << 4)) { if (k > 0 && u > 0 && r > 0 && o > 0) { int d0 = dpc + 1; if (dp[nxt][k - 1][u - 1][r - 1][o - 1] < d0) dp[nxt][k - 1][u - 1][r - 1][o - 1] = d0; } } } } cur ^= 1, nxt ^= 1; } int maxd = 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++) if (maxd < dp[cur][k][u][r][o]) maxd = dp[cur][k][u][r][o]; printf("%d\n", maxd); return 0; }