3024: 判断整除（线性动规）

解题思路:

先来说一下题意，n个数，每个数前面随意加上+-号（当然+号等于没加），然后所有的数相加，判断和是否为k的整数。
两种方法，一个是使用dfs深搜，将每种情况都进行尝试，时间复杂度2^n，能过本网站数据，数据量大的时候会超时。

还有一种是dp，这是最好的方法。

dfs代码：

#include <bits/stdc++.h>

using namespace std;

int p[10007];
int n,m,vis=0;

void dfs(int k) {
	if(k==n) {//全部更改过位置 
		int z=0;
		for(int i=0; i<n; i++) {
			z+=p[i];
		}
		if(z%m==0)vis=1;//如果可以整除
		return; 
		
	} else {
		for(int i=0; i<2; i++) {
			if(i&1) {
				dfs(k+1);
			} else {
				p[k]*=-1;
				dfs(k+1);
				p[k]*=-1;
			}
		}
	}

}

int main () {

	cin>>n>>m;
	for(int i=0; i<n; i++) {
		cin>>p[i];
	}
	dfs(0);
	cout<<(vis?"YES":"NO"); 

	return 0;
}

来详细说一下dp代码，dp[i][j]为前i个数是否可以被j整除，1表示可以，0不可以。

因为最后所有的值是要相加在一起的，所以最后的值依赖于前面的情况。

以第二个数为例，如果想要第一个数加上第二个数后sum对k取余值为j，那么第一个数p1只有两种情况，一个是p1==j-a2，一个是p1==j+a2（这里对p2前加（-）号）

推广到所有的数身上，想要加到第i个数sum%k的值为j，那么加到第i-1个数时必须满足两种情况（j-pi或者j+pi）中的一个，这样在加上第i个数或减去第i个数后和sum才为j，j%k=j（j<k）。

根据（a+b）%k=（a%k+b%k）%k，可以先进行取余后处理，一方面可以减少数组开销另一方面确保j<k。

这样我们就可以写递推式了，dp[i][j]代表的是前i个数是否可以被j整除，dp[i][j]就和（dp[i-1][(j+p[i])%k]、dp[i-1][(j-p[i])%k]）有关了，只有这两个中的一个为真，dp[i][j]才为真。

递推式：dp[i][j]=dp[i-1][(j+p[i]+k)%k] || dp[i-1][(j-p[i]+k)%k]

两个做或运算，有真则真，注意这里分别+k，是为了防止j-p[i]为数组下标为负数的情况。

根据同余 (j-p[i]+k)%k=(j-p[i])%k+k%k=(j-p[i])%k

dp代码：

#include <bits/stdc++.h>

using namespace std;

int p[10007];
bool dp[10007][107];
int n,k;

int main () {

	cin>>n>>k;
	for(int i=1; i<=n; i++) {
		cin>>p[i];
		p[i]%=k;
	}
	dp[0][0]=1;//边界，记为1
	for(int i=1; i<=n; i++) {
		for(int j=0; j<k; j++) {
			dp[i][j]=dp[i-1][(j+p[i]+k)%k]||dp[i-1][(j-p[i]+k)%k];
		}
	}
	cout<<(dp[n][0]?"YES":"NO");//dp[n][0]表示前n个数相加，对k取余余数为0，即：前n个数相加有可以整除k的情况

	return 0;
}

dp的核心是dp[i][j]为前i个数是否可以被j整除，这是本题的核心。

以上。