POJ 1745 Divisibility
DP強化週間。
長さNの数列が与えられる。数字間を+か-で計算していき、
その結果がKで割り切れるか調べよ、という問題。
いかにもなDP。雪だるま式に書くより、メモ化再帰の方が直感的だった。他の人は雪だるま式に書いてるとこが多いみたい。
dp[i+1][j]:=(i番目までの数列の加減算をmod Kしてjになるか)のbool DP。再帰関数内でmodしたものがマイナスにならないように大きいKの倍数を足して再帰している。
以下ソース。けっこう時間ギリギリだった。
bool dp[10001][100]; int a[10000]; int N, K; void dfs(int i, int m){ m %= K; if(dp[i][m]) return; dp[i][m] = true; if(i == N) return; dfs(i + 1, m + a[i] + 10000 * K); dfs(i + 1, m - a[i] + 10000 * K); } int main(int argc, char **argv){ memset(dp, false, sizeof(dp)); cin >> N >> K; for(int i = 0; i < N; i++) cin >> a[i]; dfs(0, 0); if(dp[N][0]) cout << "Divisible" << endl; else cout << "Not divisible" << endl; return 0; }
最初、dp[i][m] = true;とif(i == N) return;を
逆に書いていたのでどうしても答えが合わなかった。
少しずつできるようになってきたと思う。やったー。
Get up! 明日のSUPER ST@R!