2.6基本算法之动态规划2989:糖果

描述

由于在维护世界和平的事务中做出巨大贡献，Dzx被赠予糖果公司2010年5月23日当天无限量糖果免费优惠券。在这一天，Dzx可以从糖果公司的N件产品中任意选择若干件带回家享用。糖果公司的N件产品每件都包含数量不同的糖果。Dzx希望他选择的产品包含的糖果总数是K的整数倍，这样他才能平均地将糖果分给帮助他维护世界和平的伙伴们。当然，在满足这一条件的基础上，糖果总数越多越好。Dzx最多能带走多少糖果呢？
注意：Dzx只能将糖果公司的产品整件带走。

答案:

#include<bits/stdc++.h>
using namespace std;
int a[1000005];
int dp[1005][1005];//dp[i][j]:从i种糖果中选,组成糖果总数量k的倍数
int main(){
	int n,k;
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[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 i=1;i<=n;i++){//从i种糖果中选
		for(int j=0;j<k;j++){//求余数从0开始到k-1结束 
			//1.不选 
			if(j-a[i]%k>=0){
				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]);
			}
		}
	}
	cout<<dp[n][0];
	return 0;
}

感谢大家的不取关！我   来吗？？？   回来了！