第11回情オリ本選対策14日目(あと使えるのは1日!)
明日が使えるという意見と使えないという意見があります。昨日は体調崩したりしていた。
POJ 3254、よく考えたら一昨日考えた解法間違ってたので、改めて書く。サンプルケースも通るのに何故かWA。何故だーーーーー
以下誤ソース。誰かデバッグしてー!(懇願)
#include <cstdio> #include <vector> #include <climits> using namespace std; int main() { int N, M; scanf("%d %d\n", &M, &N); vector<bool> fertile; fertile.reserve(M * N); for (int i = 0; i < M; ++i) { for (int j = 0; j < N; ++j) { int t; scanf("%d", &t); fertile.push_back((bool)t); } } // sentinel M++; fertile.reserve(M * N); for (int i = 0; i < N; ++i) fertile.push_back(false); const int MODULO = 100000000; vector<vector<int> > dp(2, vector<int>(1 << (N + 1), 0)); int cur = 0, prev = 1; for (int i = 0, l = (1 << (N + 1)); i < l; ++i) { bool f = false; for (int j = 0; j < N + 1; ++j) { if (!(i & (1 << j))) continue; if (!fertile[N - j]) { f = true; break; } } if (f) continue; for (int j = 1; j < N; ++j) { if ((i & (3 << j)) == (3 << j)) { f = true; break; } } if (f) continue; if ((i & (1 << N)) && (i & 1)) continue; dp[prev][i] = 1; } for (int i = N + 1; i < fertile.size(); ++i) { for (int j = 0, l = (1 << (N + 1)); j < l; ++j) { if (j & 1) { if ((((j & 3) == 3) && (i % N != 0)) || (j & (1 << N)) || !fertile[i]) { dp[cur][j] = 0; } else { dp[cur][j] = (dp[prev][(1 << N) + (j >> 1)] + dp[prev][j >> 1]) % MODULO; } } else { dp[cur][j] = (dp[prev][(1 << N) + (j >> 1)] + dp[prev][j >> 1]) % MODULO; } } cur = !cur, prev = !prev; } int res = 0; for (int i = 0, l = (1 << (N + 1)); i < l; ++i) res = (res + dp[cur][i]) % MODULO; printf("%d\n", res); return 0; }