动态规划 ---- 闫式DP分析法
状态表示: f[i][j]
集合:从i个数中选总和%10=j的方案
属性:最大值
状态计算: ---- 集合的划分
划分依据:是否包含第i个数
1.包含第i个数 ---- f[i - 1, j - w % k] + w
2.不包含第i个数 ---- f[i - 1][j]
j-w%k
有可能是负数,通过(j-w%k+k)%k
转换成正的
#include <bits/stdc++.h>
using namespace std;
const int N=110;
int a[N],f[N][N];
int n,k;
int main()
{
cin>>n>>k;
memset(f,-0x3f,sizeof f);//f[0][1]、f[0][2]···无意义
f[0][0]=0; //本题求的是最大值而不是方案数,因此为0
for(int i=1;i<=n;i++)
{
int w;
cin>>w;
for(int j=0;j<=k;j++)
f[i][j]=max(f[i-1][j],f[i-1][(j-w%k+k)%k]+w)
}
cout<<f[n][0];
return 0;
}