题意:一个长为 N 的序列(每个元素的绝对值不超过10000),为其中间的 N - 1 个位置添加 "+" 或者 "-",问能否使得最后的数能被 K 整除(1 <= N <= 10000, 2 <= K <= 100) 。
题目链接:http://poj.org/problem?id=1745
——>>这题和poj - 1722很像,不同点在于这题的 N 变大了100倍,但是,相应地,dp的第二维其实变小了100倍(可对K取模)。。
状态:dp[i][j] 表示前 i 个数合成模 K 为 j 是否可行
状态转移方程:
dp[i + 1][((j + a[i + 1]) % K + K) % K] = 1;
dp[i + 1][((j - a[i + 1]) % K + K) % K] = 1;
#include <cstdio> #include <cstring> const int MAXN = 10000 + 10; const int MAXK = 100 + 10; int N, K; int a[MAXN]; char dp[MAXN][MAXK]; void Read() { for (int i = 1; i <= N; ++i) { scanf("%d", a + i); } } void Dp() { memset(dp, 0, sizeof(dp)); dp[1][(a[1] % K + K) % K] = 1; for (int i = 1; i < N; ++i) { for (int j = 0; j < K; ++j) { if (dp[i][j] != 0) { dp[i + 1][((j + a[i + 1]) % K + K) % K] = 1; dp[i + 1][((j - a[i + 1]) % K + K) % K] = 1; } } } dp[N][0] == 0 ? puts("Not divisible") : puts("Divisible"); } int main() { while (scanf("%d%d", &N, &K) == 2) { Read(); Dp(); } return 0; }