Description

【题意】数据byscy20231024
有 $N$ 个数 $a_i$ ，从中选若干个使其总和是 $k$ 的倍数，求选出的数的总和的最大值。

【输入】
第一行包含两个整数 $N(1 \le N \le 10000)$ 和 $K(1 \le K \le 200)$。
下来 $N$ 个整数 $a_i \ ( 0 \le a_i \le 10^6)$。

【输出】
符合要求的总数，如果不能达到K的倍数这一要求，输出0。

【样例输入】
5 7
1 2 3 4 5

【样例输出】
14

【提示】
选择2+3+4+5=14，这样总数是7的倍数，并且是总数最多的选择。

Hint

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10,K=2e2+10;
long long f[N][K],a[N];
int main()
{
    //freopen("a.in","r",stdin);freopen("a.out","w",stdout);
    int n,k;scanf("%d%d",&n,&k);
	for(int i=1;i<=n;++i)scanf("%lld",&a[i]);
	memset(f,-63,sizeof(f));
	for(int i=0;i<=n;i++)f[i][0]=0;
	for(int i=1;i<=n;i++)
		for(int j=0;j<=k-1;j++)
		{
			f[i][(j+a[i])%k]=max(f[i][(j+a[i])%k],f[i-1][(j+a[i])%k]);
			f[i][(j+a[i])%k]=max(f[i][(j+a[i])%k],f[i-1][j]+a[i]);
		}
    printf("%lld\n",f[n][0]);
    return 0;
}

奇怪省空间小作伐by hansang:

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10, M=210;
typedef long long LL;
const LL P=1e8;
LL a[N], f[2][M];
int main(){
	int n, m; scanf("%d%d", &n, &m);
	for(int i=1; i<=n; i++) scanf("%lld", &a[i]);
	memset(f, -0x3f, sizeof(f)); int t=0;
	f[1][0]=0; LL inf=f[0][0];
	for(int i=1; i<=n; i++){
		for(int j=0; j<m; j++){
			int d=(j-a[i]%m+m)%m;
			f[t][j]=max({f[t^1][j], f[t^1][d]+(d+a[i])/m});
		}
		f[t][a[i]%m]=max(f[t][a[i]%m], a[i]/m);
		t^=1;
	}
	printf("%lld\n", f[t^1][0]*m);
	return 0;
}