結果
問題 | No.291 黒い文字列 |
ユーザー |
|
提出日時 | 2017-06-08 17:28:43 |
言語 | D (dmd 2.109.1) |
結果 |
AC
|
実行時間 | 935 ms / 2,000 ms |
コード長 | 1,427 bytes |
コンパイル時間 | 629 ms |
コンパイル使用メモリ | 94,608 KB |
実行使用メモリ | 111,980 KB |
最終ジャッジ日時 | 2024-06-12 19:49:26 |
合計ジャッジ時間 | 6,157 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 26 |
ソースコード
import std.algorithm, std.conv, std.range, std.stdio, std.string; void main() { auto s = readln.chomp; int n = s.length.to!int, n5 = n / 5; auto dp = new int[][][][][](n+1, n5+1, n5+1, n5+1, n5+1); foreach (i; 0..n+1) foreach (k; 0..n5+1) foreach (ku; 0..n5+1) foreach (kur; 0..n5+1) dp[i][k][ku][kur][] = -1; int calc(int i, int k, int ku, int kur, int kuro) { if (dp[i][k][ku][kur][kuro] >= 0) return dp[i][k][ku][kur][kuro]; if (i >= n) return 0; int r; int calcN() { return calc(i+1, k, ku, kur, kuro); } int calcK() { return calc(i+1, min(k+1, n5), ku, kur, kuro); } int calcKu() { return k > 0 ? calc(i+1, k-1, min(ku+1, n5), kur, kuro) : calcN(); } int calcKur() { return ku > 0 ? calc(i+1, k, ku-1, min(kur+1, n5), kuro) : calcN(); } int calcKuro() { return kur > 0 ? calc(i+1, k, ku, kur-1, min(kuro+1, n5)) : calcN(); } int calcKuroi() { return kuro > 0 ? calc(i+1, k, ku, kur, kuro-1) + 1 : calcN(); } switch (s[i]) { case 'K': r = calcK(); break; case 'U': r = calcKu(); break; case 'R': r = calcKur(); break; case 'O': r = calcKuro(); break; case 'I': r = calcKuroi(); break; case '?': r = max(calcK(), calcKu(), calcKur(), calcKuro(), calcKuroi()); break; default: r = calcN(); break; } return dp[i][k][ku][kur][kuro] = r; } writeln(calc(0, 0, 0, 0, 0)); }