AOJ0559 JOI Flag
bitDP初めてなのにこれをやったせいで苦戦しました.
JOIの解説を読まないと解けませんでした...
これだと解けるけどAOJではMLEします
#include <cstdio> #include <cstring> using namespace std; const int mod = 100000; int n, m, count; char flag[21][21]; int fact[401]; int dp[20][20][10947][2]; int rec(int v, int isJ, int S){ int x, y; x = v / m; y = v % m; if (v == n * m){ return 1; } if(dp[x][y][S][isJ] >= 0){ return dp[x][y][S][isJ]; } int tmp = 0; if (flag[x][y] == '?' || flag[x][y] == 'J'){ int bit = S; bit = bit << 1 & ((1 << (m - 1)) - 1); tmp = (rec(v + 1, 1, bit) + tmp) % mod; } if (flag[x][y] == '?' || flag[x][y] == 'O'){ int bit = S; if(isJ == 1){ bit = (bit << 1 & ((1 << (m - 1)) - 1)) | 1; }else{ bit = bit << 1 & ((1 << (m - 1)) - 1); } tmp = (rec(v + 1, 0, bit) + tmp) % mod; } if (flag[x][y] == '?' || flag[x][y] == 'I'){ if (((1 << (m - 2)) & S) == 0 || y == m - 1){ int bit = S; bit = bit << 1 & ((1 << (m - 1)) - 1); tmp = (rec(v + 1, 0, bit) + tmp) % mod; } } return dp[x][y][S][isJ] = tmp; } int main(){ fact[0] = 1; for(int i = 1; i <= 400; i++){ fact[i] = (fact[i - 1] * 3) % mod; } scanf("%d %d", &n, &m); getchar(); for (int i = 0; i < n; i++){ for (int j = 0; j < m; j++){ scanf("%c", &flag[i][j]); if (flag[i][j] == '?'){ count++; } } getchar(); } memset(dp, -1, sizeof(dp)); printf("%d\n", (fact[count] - rec(0,0,0)) % mod); return 0; }
さらにisJとSの情報をまとめてひとつの要素にするかforループで配列を使い回すと通ります