郑州哪里有做网站,网站改版需要注意什么,长沙百度网站推广,广州网站建设推广公司有哪些描述
由于在维护世界和平的事务中做出巨大贡献#xff0c;Dzx被赠予糖果公司2010年5月23日当天无限量糖果免费优惠券。在这一天#xff0c;Dzx可以从糖果公司的N件产品中任意选择若干件带回家享用。糖果公司的N件产品每件都包含数量不同的糖果。Dzx希望他选择的产品包含的糖…描述
由于在维护世界和平的事务中做出巨大贡献Dzx被赠予糖果公司2010年5月23日当天无限量糖果免费优惠券。在这一天Dzx可以从糖果公司的N件产品中任意选择若干件带回家享用。糖果公司的N件产品每件都包含数量不同的糖果。Dzx希望他选择的产品包含的糖果总数是K的整数倍这样他才能平均地将糖果分给帮助他维护世界和平的伙伴们。当然在满足这一条件的基础上糖果总数越多越好。Dzx最多能带走多少糖果呢 注意Dzx只能将糖果公司的产品整件带走。
答案:
#includebits/stdc.h
using namespace std;
int a[1000005];
int dp[1005][1005];//dp[i][j]:从i种糖果中选,组成糖果总数量k的倍数
int main(){int n,k;cinnk;for(int i1;in;i){cina[i];}memset(dp,-0x3f,sizeof(dp));/*边界条件:dp[i][j]初始化为负无穷,除了dp[0][0]为0,因为我们这里求的是最大值,另外,必须保证所有的状态是由dp[0][0]转移过来的*/dp[0][0]0;//dp[0][0]边界条件:0种糖果组成糖果总数量0的倍数是0 for(int i1;in;i){//从i种糖果中选for(int j0;jk;j){//求余数从0开始到k-1结束 //1.不选 if(j-a[i]%k0){dp[i][j]max(dp[i-1][j],dp[i-1][j-a[i]%k]a[i]);}//2.选 else{dp[i][j]max(dp[i-1][j],dp[i-1][k-abs(j-a[i]%k)]a[i]);}}}coutdp[n][0];return 0;
}
感谢大家的不取关我 来吗 回来了
