POJ:
A完这题去买福鼎肉片,和舍友去买滴~舍友感慨“这一天可以卖好几百份,每份就算赚一块钱。。那么一个月。。一年。。。”
我说“那我们以后去卖这个吧,饿了还能自己煮着吃”
哈哈,一群天真的少年呀~~~~
说正事~
------------------------------------------------华丽的分割线-------------------------------------------------
题目大意:
给一串数列,在其中间插入+或者-可以得到不同的结果,你需要判断的是对于n个这样的数经过一系列运算后最终是否能得到k。(每个数都要用,按题目给的顺序)
思路:
DP,本题的精华在于用位向量来表示是否出现过mod k的余数,最后判断0那个位置是否出现即可。
还可以直接用两个一维数组来优化空间复杂度,不过时间略长一些。(世界是公平的,有舍才有得)
1.未优化空间复杂度 141ms
#include#include 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
2.优化了的版本 157MS
#include#include 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