题意：输入n个有序数字，数字前可加上+或-,求是否存在这样的和，使得该和能够整除数字k
每个数字前只有取正或负两种情况，所以符合0，，1背包，而且背包的重量是除k的余数（均是正数）
//172 KB297 msC++785 B#include<cstdio>#include<cstring>#include<algorithm>#include<iostream>using namespace std;int num[10010];bool dp[2][105];int n,mod;int main(){while(~scanf("%d%d",&n,&mod)){memset(dp,0,sizeof(dp));dp[0][0]=true;for(int i=1;i<=n;i++) scanf("%d",&num[i]);for(int i=1;i<=n;i++){memset(dp[i&1],0,sizeof(dp[i&1]));for(int j=0;j<mod;j++){int t1=(j+num[i]+10000*mod)%mod;int t2=(j-num[i]+10000*mod)%mod;dp[i&1][t1]=max(dp[i&1][t1],dp[(i-1)&1][j]);dp[i&1][t2]=max(dp[i&1][t2],dp[(i-1)&1][j]);}}if(dp[n&1][0]) printf("Divisible\n");else printf("Not divisible\n");}return 0;}
自己战胜自己是最可贵的胜利。
