首页 > 代码库 > noi 2989 糖果
noi 2989 糖果
题目链接：http://noi.openjudge.cn/ch0206/2989/
首先，数据很大，直接用背包会re。
这里增加的是对%k 的余数维度。f[i][j] 表示前 i 种糖果取到总颗数模 k 余数为 j 的最大颗数。
注意一定要先将 f[i-1][j] 转移到 f[i][j] ，再枚举余数dp，不然会有重叠。答案是 f[n][0];
#include <bits/stdc++.h>using namespace std;int a[1050];int d[1001000];int f[110][110];/*int main(){ int n,k; int sum = 0; scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); sum+=a[i]; } int t = sum/k; sum = t*k; for(int i=1;i<=n;i++) { for(int j=sum;j>=0;j--) { if(j>=a[i]) { d[j] = max(d[j],d[j-a[i]]+a[i]); } } } bool flag = false; for(;;) { if(d[sum]%k==0) { printf("%d\n",d[sum]); flag = true; break; } else sum = sum - k; } if(!flag) puts("0"); return 0;}*/int main(){ int n,k; scanf("%d%d",&n,&k); memset(f,0,sizeof(f)); for(int i=1; i<=n; i++) scanf("%d",&a[i]); for(int i=1; i<=n; i++) { for(int q=0; q<=k-1; q++) f[i][q]=f[i-1][q]; for(int j=0; j<=k-1; j++) if(f[i-1][j]+a[i]>f[i][(f[i-1][j]+a[i])%k]) f[i][(f[i-1][j]+a[i])%k]=f[i-1][j]+a[i]; } printf("%d",f[n][0]); return 0;}
noi 2989 糖果
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。