首页 > 代码库 > poj 1745 Divisibility (dp)
poj 1745 Divisibility (dp)
//给你n个数,两个数之间可以+。-两个运算 得出的所有结果只要有能被k正除,输出Divisible,否则Not divisible # include <iostream> # include <stdio.h> # include <algorithm> # include <string.h> using namespace std; int dp[10010][110];//第一维代表几个数相加,第二位为几个数相加%k后的余数 int b[10010]; int main() { int n,k,i,j,t; while(~scanf("%d %d",&n,&k)) { for(i=1; i<=n; i++) scanf("%d",&b[i]); for(i=0; i<=n; i++) for(j=0; j<=k-1; j++) dp[i][j]=0; dp[0][0]=1; for(i=1; i<=n; i++) { for(j=0; j<=k-1; j++) { if(dp[i-1][j]==1) { t=((j+b[i])%k+k)%k;//可能有负数,注意取余 dp[i][t]=1; t=((j-b[i])%k+k)%k; dp[i][t]=1; } } } if(dp[n][0]==1) printf("Divisible\n"); else printf("Not divisible\n"); } return 0; }
poj 1745 Divisibility (dp)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。