# AtCoder Beginner Contest 281 D
题意
从一个大小为N的数组中选择K个数,使得这K个数的和是D的最大倍数。
题解
有数据范围1<=K<=N<=100,D<=100可知,这是个简单dp.
nt n,m,K,D;
int f[110][110];
int a[110];
void solve()
{
//f[i][j][k]表示前i个数选取j个,和余数为k的最大值
//所求为f[n][K][0],x=a[i]%D;
//如果f[i-1][j-1][k-x]!=-1 f[i][j][k]=max(f[i][j][k],f[i-1][j-1][k-x]+a[i])
//else f[i][j][k]=f[i-1][j][k];
cin>>n>>K>>D;
memset(f,-1,sizeof(f));
for(int i=0;i<=n;i++) f[0][i]=0;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++)
{
int x=a[i]%D;
for(int j=min(i,K);j>=1;j--)
{
for(int k=D-1;k>=x;k--)
{
if(f[j-1][k-x]==-1) continue;
int tmp=(f[j-1][k-x]+a[i])%D;
if(tmp==k)
{
f[j][k]=max(f[j-1][k-x]+a[i],f[j][k]);
}
}
for(int k=x-1;k>=0;k--)
{
int d=(k-x+D)%D;
if(f[j-1][d]==-1) continue;
int tmp=(f[j-1][d]+a[i])%D;
if(tmp==k)
{
f[j][k]=max(f[j-1][d]+a[i],f[j][k]);
}
}
}
}
cout<<f[K][0]<<endl;
}
标签:tmp,ABC,int,max,--,110,281
From: https://www.cnblogs.com/LIang2003/p/17107875.html