崔凯 本地wordpress,东莞seo整站优化,网站怎么更换页面图片,洛阳网站制作POJ:http://poj.org/problem?id1745 A完这题去买福鼎肉片#xff0c;和舍友去买滴~舍友感慨“这一天可以卖好几百份#xff0c;每份就算赚一块钱。。那么一个月。。一年。。。” 我说“那我们以后去卖这个吧#xff0c;饿了还能自己煮着吃” 哈哈#xff0c;一群天真的少… POJ:http://poj.org/problem?id1745 A完这题去买福鼎肉片和舍友去买滴~舍友感慨“这一天可以卖好几百份每份就算赚一块钱。。那么一个月。。一年。。。” 我说“那我们以后去卖这个吧饿了还能自己煮着吃” 哈哈一群天真的少年呀~~~~ 说正事~ ------------------------------------------------华丽的分割线------------------------------------------------- 题目大意 给一串数列在其中间插入或者-可以得到不同的结果你需要判断的是对于n个这样的数经过一系列运算后最终是否能得到k。每个数都要用按题目给的顺序 思路: DP本题的精华在于用位向量来表示是否出现过mod k的余数最后判断0那个位置是否出现即可。 还可以直接用两个一维数组来优化空间复杂度,不过时间略长一些。世界是公平的有舍才有得 1.未优化空间复杂度 141ms #includecstdio
#includecstring
const int MAXN1000010;
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 i1;in;i){scanf(%d,temp);for(int j0;jk;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 #includecstdio
#includecstring
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 i1;in;i){bool temp[101]{0};scanf(%d,value);for(int j0;jk;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);}
} 转载于:https://www.cnblogs.com/murmured/p/5004234.html
