Source

https://atcoder.jp/contests/abc281/tasks/abc281_d

Idea

由于选择引发的DP问题(背包问题)。不妨令\(dp[i][j][k]\)表示从\(a_1..a_i\)中选出来\(j\)个元素，使得他们的和除以\(D\)是等于\(k\)的（或者\(-1\)，如果不可能的话）。

状态转移：

• 不选：dp[i+1][j][k] = max(dp[i+1][j][k],dp[i][j][k]);
• 选：dp[i+1][j+1][(k+a[i])%D] = max(dp[i+1][j+1][(k+a[i])%D],dp[i][j][k]+a[i]);

Code

#include<bits/stdc++.h>
#define F(i, q, b) for(int i=q;i<=b;i++)
#define Fd(i, q, b) for(int i=q;i>=b;i--)
#define MAXN 1000005
//#define MMAX(a, b) if(b>a){printf("%d %d\n", b,a); a=b; }
#define MMAX(a, b) if(b>a){a=b; }
#define int long long 
using namespace std;
int a[105];
int dp[105][105][105];
signed main(){
	int N, K, D; cin>>N>>K>>D;
	F(i, 1, N) cin>>a[i];
	F(i, 0, 104) F(j, 0, 104) F(k, 0, 104) dp[i][j][k]=-1;
	dp[1][1][0]=dp[1][0][0]=0;
	F(i, 1, N) F(j, 1, K+1) F(k, 0, D-1){
		if(dp[i][j][k] == -1) continue;
		MMAX(dp[i+1][j][k], dp[i][j][k]);
		MMAX(dp[i+1][j+1][(k+a[i])%D], dp[i][j][k]+a[i]);
		
	} 
	cout<<dp[N+1][K+1][0]<<endl;
}