題意：給出n,k,n個(gè)數(shù)，在這n個(gè)數(shù)之間任意放置+,-號(hào)，稱得到的等式的值能夠整除k則為可劃分的，否則為不可劃分的。

自己想的是枚舉，將所有得到的等式的和算出來(lái)，再判斷它是否能夠整除k，可是有10000個(gè)數(shù)-_-

5555---還是看的題解--

話說(shuō)這樣的狀態(tài)好奇妙啊啊啊---

用dp[i][j]表示等式中有i個(gè)數(shù)的時(shí)候余數(shù)為j是否成立，成立的話dp[i][j]的值為1，否則為0

然后就是遞推的過(guò)程， 如果dp[i-1][j]為1，那么dp[i][(j-a[i])%k]=1,dp[i][(j+a[i])%k]=1； 最后再判斷dp[n][0]是否為1

1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 7 int dp[10005][105],a[10005],n,k; 8 9 int getmod(int x) 10 { 11 if(x<0) return (-x)%k; 12 return x%k; 13 } 14 15 int main() 16 { 17 int i,j; 18 while(scanf("%d %d",&n,&k)!=EOF) 19 { 20 for(i=1;i<=n;i++) scanf("%d",&a[i]); 21 dp[1][getmod(a[1])]=1; 22 23 for(i=2;i<=n;i++) 24 { 25 for(j=0;j<k;j++) 26 { 27 if(dp[i-1][j]) dp[i][getmod(j-a[i])]=dp[i][getmod(j+a[i])]=1; 28 } 29 } 30 if(dp[n][0]) printf("Divisible\n"); 31 else printf("Not divisible\n"); 32 } 33 return 0; 34 } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/wuyuewoniu/p/4297520.html

總結(jié)

以上是生活随笔為你收集整理的POJ 1745 Divisibility【DP】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。