2989:糖果

【题目链接】

　　　　http://noi.openjudge.cn/ch0206/2989/

【算法】

　　　　定义好状态即可：前i种产品模k余j的最大数量。代码写的较烦，可以初始化为负无穷然后直接dp【i】【j】=max（dp【i-1】【j】，dp【i-1】【（j+k-a【i】%k）%k】）。

【代码】

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int n,k,i,j,m;
 4 int a[110],dp[110][110];
 5 int main()
 6 {
 7     scanf("%d%d",&n,&k);
 8     for(i=1;i<=n;i++) scanf("%d",&a[i]);
 9     dp[1][a[1]%k]=a[1];
10     for(i=2;i<=n;i++)
11     for(j=0;j<k;j++) {
12         if(a[i]%k==0) dp[i][j]+=a[i]+dp[i-1][j];
13         else if(dp[i-1][(j+k-a[i]%k)%k]||a[i]%k==j)
14             dp[i][j]=max(dp[i-1][j],a[i]+dp[i-1][(j+k-a[i]%k)%k]);
15         else
16             dp[i][j]=dp[i-1][j];
17     }
18     printf("%d
",dp[n][0]);
19     return 0;
20 }