POJ 1745：Divisibility 枚舉某一狀態的DP

POJ 1745：Divisibility 枚舉某一狀態的DP

 

Divisibility Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 11001   Accepted: 3933

 

Description

Consider an arbitrary sequence of integers. One can place + or - operators between integers in the sequence, thus deriving different arithmetical expressions that evaluate to different values. Let us, for example, take the sequence: 17, 5, -21, 15. There are eight possible expressions: 17 + 5 + -21 + 15 = 16
17 + 5 + -21 - 15 = -14
17 + 5 - -21 + 15 = 58
17 + 5 - -21 - 15 = 28
17 - 5 + -21 + 15 = 6
17 - 5 + -21 - 15 = -24
17 - 5 - -21 + 15 = 48
17 - 5 - -21 - 15 = 18
We call the sequence of integers divisible by K if + or - operators can be placed between integers in the sequence in such way that resulting value is divisible by K. In the above example, the sequence is divisible by 7 (17+5+-21-15=-14) but is not divisible by 5.

You are to write a program that will determine divisibility of sequence of integers.

Input

The first line of the input file contains two integers, N and K (1 <= N <= 10000, 2 <= K <= 100) separated by a space.
The second line contains a sequence of N integers separated by spaces. Each integer is not greater than 10000 by it's absolute value.

Output

Write to the output file the word Divisible if given sequence of integers is divisible by K or Not divisible if it's not.

Sample Input

4 7
17 5 -21 15

Sample Output

Divisible

題意就是給了N個數，在N-1個位置變換+ -號，問得到的結果中有沒有能夠整除K的，如果有，輸出Divisible。沒有，輸出Not Divisible。

DP真是一片很深的海。

越做DP越覺得DP的花樣很多，這個是我做了POJ1837覺得DP是可以做這道題的。覺得DFS也應該可以，沒試。。。

POJ1837和這道題都是固定枚舉其中的某個狀態或者變量，這裡的可以枚舉的狀態就是余數，給了K，所以我只需對0到K-1這些余數做枚舉，然後從i的余數狀態推i+1的余數狀態。

就是這樣：

dp[i][(j+value[i])%mod] +=dp[i-1][j];
dp[i][(j-value[i]+mod)%mod] +=dp[i-1][j];

然後這樣做可能是因為數目比較大了溢出還是怎樣WA了一次，於是我控制了一下數值。這樣：

dp[i][(j+value[i])%mod] +=dp[i-1][j];
dp[i][(j-value[i]+mod)%mod] +=dp[i-1][j];


if(dp[i][(j+value[i])%mod]>10)
dp[i][(j+value[i])%mod]=10;
if(dp[i][(j-value[i]+mod)%mod]>10)
dp[i][(j+value[i])%mod]=10;

。。。很幼稚的方法，但還是漲姿勢長見識了。。。

代碼：

 

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

int num,mod;
int dp[10005][102];
int value[10005];

int main()
{
	int temp,i,j;
	cin>>num>>mod;

	cin>>value[1];
	value[1]=abs(value[1])%mod;
	for(i=2;i<=num;i++)
	{
		cin>>temp;
		value[i]=abs(temp);
		value[i]=value[i]%mod;
	}
	memset(dp,0,sizeof(dp));
	dp[1][value[1]]=1;

	for(i=2;i<=num;i++)
	{
		for(j=0;j10)
				dp[i][(j+value[i])%mod]=10;
			if(dp[i][(j-value[i]+mod)%mod]>10)
				dp[i][(j+value[i])%mod]=10;
		}
	}
	if(dp[num][0])
	{
		cout<