poj 1745问题

题意：给你n个整数，和一个k值（2<=k<=100)，问在这n个数之间的n-1的位置任意放加减号，问有没有一种情况使结果整除k。

思路：  dp[i][j]=dp[i-1][j-a[i]]||dp[i-1][j+a[i]];这里用到了数论里的一点知识，sum(a[i])%k = sum(a[i]%k)%k,假设dp[i][j]为取前i个数求和时余数为j的情况。只要dp[4][0]=1就表示能够整除。

代码如下：

#include <iostream>
using namespace std;
int a[10001];
int dp[10001][101];

int main()
{
	int n,m,s,t,i,j;
	cin>>n>>m;
	for(i=1;i<=n;i++)
		cin>>a[i];
	s=a[1];
	while(s<0)
		s+=m;
	dp[1][s%m]=1;
	for (i=2;i<=n;i++)
	{
		for (j=0;j<m;j++)
		{
			s=j-a[i];
			while(s<0)
				s+=m;
			t=j+a[i];
			while(t<0)
				t+=m;
			dp[i][j]=dp[i-1][s%m]||dp[i-1][t%m];//状态转移方程
		}
	}
	if (dp[n][0])
		cout<<"Divisible"<<endl;
	else
		cout<<"Not Divisible"<<endl;
	return 0;
}