动态规划回溯法

POJ1745总结

Divisibility

题目来源

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

我的代码

要求A+B是否整除K,即(A+B) mod k =? 0,等价于((A mod k)+B) mod k=? 0,所以在搜索到第i个数时,如果此时的和mod k的余数已经在之前的搜索这一步时出现过,就不要再往下搜索了,结果都是一样的。实现方法是设dp[i][j],当搜索第i个数时如果余数为j就将dp[i][j]赋值为1。

#include<stdio.h>
#include<string.h>

const int operat[2]={1,-1};
int n,k,sum;
int dp[10010][110];
int integers[10010];

int dfs(int step){
	if (step==n){
		if (dp[n-1][0]==1) return 1;
	}else{
		for (int i=0;i<2;i++){
			sum+=operat[i]*integers[step];
			//没处理和为负数的情况 
			if (dp[step][sum%k]==0){
				dp[step][sum%k]=1;
				if (dfs(step+1)==1) return 1;
			}
			sum-=operat[i]*integers[step];
		}
	}
	return 0;
}

int main()
{
	scanf("%d%d",&n,&k);
	memset(dp,0,sizeof(dp));
	for (int i=0;i<n;i++){
		scanf("%d",&integers[i]);
	}
	dp[0][integers[0]%k]=1;
	sum=integers[0];
	int ans=dfs(1);
	if (ans==1){
		printf("Divisible\n");
	}else{
		printf("Not divisible\n");
	}
	return 0;
}

这一天不仅可以记忆化搜索,还可以直接用动态规划,实现的方式是一样的,dp方程是dp[i][j]=dp[i-1][j-integers[i]]|dp[i-1][j+integers[i]],当然j-integers[i]要经过mod k处理。

反思

我没有处理和为负数的情况,居然没有发生数组越界。