题目大意：每个数都必须取到，相加或相减去，问所有的方案最后的得数中有没有一个方案可以整除k
这个题目的难点在于dp数组的安排上面
其实也就是手动模仿了一下
比如
一个数，不用说，第一个数之前不用加符号就是本身，那么本身直接对K取余，
那么取17的时候有个余数为2————基础
然后来了一个5，
(2 + 5)对7取余为0————层层延伸
(2 - 5)对7取余为4（将取余的负数变正）那么前2个数有余数0和4
再来一个-21
（0+21）对7取余为0
（0-21）对7取余为0
（4+21）对7取余为4
（4-21）对7取余为4
再来一个-15同样是这样
（0+15）%7 = 1
（0-15）%7 = 6
（4+15）%7 = 5
（4-15）%7 = 3
同理可以找到规律，定义dp[i][j]为前i个数进来余数等于j是不是成立，1为成立，0为不成立
所以可以定义dp[i][j]如下：对于前i个数，得出的结果除以k的余数是否为j的0，1布尔值
所以层层递推后，只要看dp[n][0]就可以啦
#include <iostream> #include <cstdio> #include <string.h> #include <algorithm> #define inf (1 << 30) using namespace std; const int maxn = 120; const int maxm = 1e4 + 10; int dp[maxm][maxn]; int a[maxm]; int posmod(int n,int k) { n = n % k; while(n < 0) { n += k; } return n; } int main() { int n,k; while(~scanf("%d%d",&n,&k)) { for(int i = 1;i <= n;i++) scanf("%d",&a[i]); // dp[i][j]表示取到第i个数除以k的余数是不是j memset(dp,0,sizeof(0)); dp[1][posmod(a[1],k)] = 1; for(int i = 2;i <= n;i++) { for(int j = 0;j < k;j++) { if(dp[i-1][j])//由一个已知的关系向上推 { dp[i][posmod(j+a[i],k)] = 1; dp[i][posmod(j-a[i],k)] = 1; } } } if(dp[n][0]) { cout<<"Divisible"<<endl; } else { cout<<"Not divisible"<<endl; } } return 0; }
感觉这个题通了一点dp的窍~~嘿嘿嘿加油