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");elseprintf("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");elseprintf("Not divisible\n");}
}