POJ 1745 Divisibility DP

POJ:http://poj.org/problem?id=1745

A完这题去买福鼎肉片，和舍友去买滴~舍友感慨“这一天可以卖好几百份，每份就算赚一块钱。。那么一个月。。一年。。。”

我说“那我们以后去卖这个吧，饿了还能自己煮着吃”

哈哈，一群天真的少年呀~~~~

说正事~

------------------------------------------------华丽的分割线-------------------------------------------------

题目大意：

给一串数列，在其中间插入+或者-可以得到不同的结果，你需要判断的是对于n个这样的数经过一系列运算后最终是否能得到k。（每个数都要用，按题目给的顺序）

思路:

DP，本题的精华在于用位向量来表示是否出现过mod k的余数，最后判断0那个位置是否出现即可。

还可以直接用两个一维数组来优化空间复杂度,不过时间略长一些。（世界是公平的，有舍才有得）

1.未优化空间复杂度 141ms

#include<cstdio>

#include<cstring>

const int MAXN=10000+10;

bool dp[MAXN][110];

int main()

{

	int n,k;

	while(~scanf("%d%d",&n,&k))

	{

		int temp;

		scanf("%d",&temp);

		memset(dp,0,sizeof(dp));

		dp[0][( temp +k*10000) %k]=1;

		for(int i=1;i<n;i++)

		{

			scanf("%d",&temp);

			for(int j=0;j<k;j++)

			{

				if(!dp[i-1][j])

					continue;

				dp[ i ][ (j + temp +k*10000) %k ]=1;

				dp[ i ][ (j - temp +k*10000) %k ]=1;

			}

		}

		if(dp[n-1][0])

			printf("Divisible\n");

		else

			printf("Not divisible\n");

	}

}

2.优化了的版本 157MS

#include<cstdio>

#include<cstring>

bool dp[101];

int main()

{

	int n,k;

	while(~scanf("%d%d",&n,&k))

	{

		int value;

		scanf("%d",&value);

		memset(dp,0,sizeof(dp));

		dp[( value +k*10000) %k]=1;

		for(int i=1;i<n;i++)

		{

			bool temp[101]={0};

			scanf("%d",&value);

			for(int j=0;j<k;j++)

			{

				if(!dp[j])

					continue;

				temp[ (j + value +k*10000) %k ]=1;

				temp[ (j - value +k*10000) %k ]=1;

			}

			memcpy(dp,temp,sizeof(temp));

		}

		if(dp[0])

			printf("Divisible\n");

		else

			printf("Not divisible\n");

	}

}

巴特西

POJ 1745 Divisibility DP

最新文章

热门文章