【题目链接】
ybt 1299：糖果
OpenJudge 2.6 2989:糖果
【题目考点】
1. 动态规划：线性动规
【解题思路】
1. 状态定义
集合：选择产品的方案
限制：在前几个产品中选择产品，糖果总数除以k后余几
属性： 糖果数量
条件：最大
统计量：糖果总数
状态定义：dp[i][j]在前i个产品中选择产品，糖果总数满足除以k余j，糖果数量最大的产品选择方案的糖果数。（如果前i个产品中选择产品，不存在方案糖果数量除以k余j，那么该值为负无穷。）
初始状态：前0个产品中选择产品，糖果总数为0，除以k余0，所以dp[0][0] = 0
除以k余其它数字的情况，是不满足条件的，所以dp[0][j]
(
0
<
j
<
k
)
(0<j<k)
(0<j<k)设为负无穷。
2. 状态转移方程
记第i个产品的糖果数为
a
i
a_i
ai?，在代码中为a[i]。
分割集合：在前i个产品中选择产品，糖果总数满足除以k余j的产品选择方案。
考虑要不要选择第i个产品
- 子集1：如果不选择第i个产品，那么只可以在前i-1个产品中选择。在前i个产品中选择产品，糖果总数满足除以k余j的产品的选择方案中，糖果数量最大的方案的糖果数，即为在前i-1个产品中选择产品，糖果总数满足除以k余j的产品选择方案中，糖果数量最大的方案的糖果数，即
dp[i][j] = dp[i-1][j]。 - 子集2：如果确定选择第i产品，假设在前i-1个产品中选择的产品的糖果总数为x，加上第i个产品的糖果数
a
i
a_i
ai?，总数为
x
+
a
i
x+a_i
x+ai?，这个数除以k应该余j，即应该有
(
x
+
a
i
)
%
k
=
(
x
%
k
+
a
i
%
k
)
%
k
=
j
(x+a_i)\%k = (x\%k+a_i\%k)\%k = j
(x+ai?)%k=(x%k+ai?%k)%k=j
( x % k + a i % k ) % k = ( j + k ) % k (x\%k+a_i\%k)\%k=(j+k)\%k (x%k+ai?%k)%k=(j+k)%k
( x % k + a i % k ) % k ? a i % k = ( j + k ) % k ? a i % k (x\%k+a_i\%k)\%k-a_i\%k=(j+k)\%k-a_i\%k (x%k+ai?%k)%k?ai?%k=(j+k)%k?ai?%k
x % k = ( j + k ? a i % k ) % k x\%k=(j+k-a_i\%k)\%k x%k=(j+k?ai?%k)%k
因此，需要先在前i-1个产品中寻找产品使得糖果总数x除k余 x % k x\%k x%k，即糖果总数除k余 ( j + k ? a i % k ) % k (j+k-a_i\%k)\%k (j+k?ai?%k)%k时，再选择第i产品，糖果总数除k才能余j。
因此，确定选择第i产品时，在前i个产品中选择产品能得到的糖果最多的方案的糖果数为：在前i-1个产品中选择产品，满足糖果数除k余 ( j + k ? a i % k ) % k (j+k-a_i\%k)\%k (j+k?ai?%k)%k时，糖果数最大的方案的糖果数，加上第i物品的糖果数，即dp[i][j] = dp[i-1][(j+k-a[i]%k)%k]+a[i] - 以上两种情况求最大值。
最后输出的结果为：在前n个产品中选择产品，糖果数满足除k余0，能得到的糖果数最多的选择方案的糖果数，即dp[n][0]。如果dp[n][0]为负数，那么输出0。
【题解代码】
解法1：动态规划：线性动规
#include<bits/stdc++.h>
using namespace std;
#define N 105
#define INF 0x3f3f3f3f
int n, k, a[N];//a[i]:第i产品的糖果数
int dp[N][N];//dp[i][j]:在前i个产品中选择产品，糖果总数满足除以k余j，糖果数量最大的产品选择方案的糖果数。
int main()
{
cin >> n >> k;
for(int i = 1; i <= n; ++i)
cin >> a[i];
dp[0][0] = 0;
for(int j = 1; j < k; ++j)
dp[0][j] = -INF;
for(int i = 1; i <= n; ++i)
for(int j = 0; j < k; ++j)
dp[i][j] = max(dp[i-1][j], dp[i-1][(j+k-a[i]%k)%k]+a[i]);
cout << (dp[n][0] > 0 ? dp[n][0] : 0);
return 0;
}
