。

在这一天#xff0c;Dzx可以从糖果公司的N件产品中任意选择若干件带回家享用。

糖果公司的N件产品每件都包含数量不同的糖果。

Dzx希望他选择的产品包含的糖…描述

由于在维护世界和平的事务中做出巨大贡献Dzx被赠予糖果公司2010年5月23日当天无限量糖果免费优惠券。

在这一天Dzx可以从糖果公司的N件产品中任意选择若干件带回家享用。

糖果公司的N件产品每件都包含数量不同的糖果。

Dzx希望他选择的产品包含的糖果总数是K的整数倍这样他才能平均地将糖果分给帮助他维护世界和平的伙伴们。

当然在满足这一条件的基础上糖果总数越多越好。

Dzx最多能带走多少糖果呢

答案:

dp[1005][1005];//dp[i][j]:从i种糖果中选,组成糖果总数量k的倍数

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

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