题目链接：http://noi.openjudge.cn/ch0206/3531/
- 总时间限制:1000ms 内存限制:65536kB
- 描述
-
一个给定的正整数序列，在每个数之前都插入+号或-号后计算它们的和。比如序列：1、2、4共有8种可能的序列：
(+1) + (+2) + (+4) = 7
(+1) + (+2) + (-4) = -1
(+1) + (-2) + (+4) = 3
(+1) + (-2) + (-4) = -5
(-1) + (+2) + (+4) = 5
(-1) + (+2) + (-4) = -3
(-1) + (-2) + (+4) = 1
(-1) + (-2) + (-4) = -7
所有结果中至少有一个可被整数k整除，我们则称此正整数序列可被k整除。例如上述序列可以被3、5、7整除，而不能被2、4、6、8……整除。注意：0、-3、-6、-9……都可以认为是3的倍数。 - 输入
- 输入的第一行包含两个数：N（2 < N < 10000）和k(2 < k< 100)，其中N代表一共有N个数，k代表被除数。第二行给出序列中的N个整数，这些整数的取值范围都0到10000之间（可能重复）。
- 输出
- 如果此正整数序列可被k整除，则输出YES，否则输出NO。（注意：都是大写字母）
- 样例输入
-
3 2 1 2 4
- 样例输出
-
NO
分析：
首先，明确一个数学公式：(a+b+c)%k=(a%k+b%k+c%k)%k。所以预处理输入数据全部模k。
然后，假设dp[i][j]表示到第i个数模k是否有可能等于j。则：
转移方程为dp[i][j]=dp[i-1][(j-a[i]+k)%k] || dp[i-1][(j+a[i])%k];
#include<stdio.h> int dp[10000][100]; int main() { int n,k,i,j; int a[10000]; scanf("%d%d",&n,&k); for(i=1;i<=n;i++) { scanf("%d",&a[i]); } dp[0][0]=1; for(i=1;i<=n;i++) { a[i]%=k; for(j=0;j<k;j++) { dp[i][j]=dp[i-1][(j-a[i]+k)%k]|dp[i-1][(j+a[i])%k]; } } if(dp[n][0]==0) { printf("NO"); }else { printf("YES"); } return 0; }
参考：
http://www.cnblogs.com/reddest/p/5996326.html
http://blog.csdn.net/neqrhk/article/details/51771699#
