POJ 题目1745 Divisibility（DP，数学）

Description

Input

Output

Sample Input

4 7
17 5 -21 15

Sample Output

Divisible

Source

Northeastern Europe 1999

思路：http://blog.csdn.net/u012860063/article/details/39233169

题意：

给出N和K，然后给出N个整数（不论正负），问在这N个数中，每两个数之间（即N - 1个位置）添加加号或者减号，然后运算的值对K取余，如果余数等于0输出Divisible，否则输出Not divisible
思路：
拿
4 7
17 5 -21 15
举例
首先一个数，不用说，第一个数之前不用加符号就是本身，那么本身直接对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[N][0]为1那么即可以组成一个数对K取余为0
初始化dp为0

然后dp[1][a[1]%k] = 1
for i = 2 to N do
for j = 0 to K do
 if(dp[i - 1][j])
  dp[i][(j + a[i])%k] = 1;
  dp[i][(j - a[i])%k] = 1;
 if end
for end
for end

#include<stdio.h>
#include<string.h>
int dp[10010][110],a[10010];
int n,k;
int fun(int num)
{
	int temp=num%k;
	if(temp<0)
		temp+=k;
	return temp;
}
int main()
{
	//int n,k;
	while(scanf("%d%d",&n,&k)!=EOF)
	{
		int i,j;
		for(i=1;i<=n;i++)
			scanf("%d",&a[i]);
		memset(dp,0,sizeof(dp));
		dp[1][fun(a[1])]=1;
		for(i=2;i<=n;i++)
		{
			for(j=0;j<k;j++)
			{
				if(dp[i-1][j])
				{
					dp[i][fun(j+a[i])]=1;
					dp[i][fun(j-a[i])]=1;
				}
			}
		}
		if(dp[n][0])
		{
			printf("Divisible\n");
		}
		else
			printf("Not divisible\n");
	}
}

POJ 题目1745 Divisibility（DP，数学）

原文：http://blog.csdn.net/yu_ch_sh/article/details/44678077