题解 | 小红取数

#include<bits/stdc++.h>
using namespace std;

using ui=unsigned int;
using ll=long long;
using ull=unsigned long long;
using i128=__int128_t;
using u128=__uint128_t;
using ld=long double;

void solve()
{//其他题解中把转移方程讲解的很透彻 我就不再赘述
//但是我发现都没有讲一个萌新比较疑惑的点吧 为什么dp的初始值要设置成极小值
//其实 当设置成极小值时 代表这个点不可达 为什么不可达呢
//dp[i][j] 表示从前i个数中挑选一部分数的和对k取模余数为j的最大值
//那么当i为0时 和为0 对k取模肯定是0 所以dp[i][1]到dp[i][k-1]的值都要设置成不合法 只有dp[0][0]是合法的
	ll n,k;
	cin >> n >> k;
	vector<ll>a(n+1,0);
	for(int i=1;i<=n;i++) cin >> a[i];
	vector<vector<ll>>dp(n+1,vector<ll>(k,-1e18));
	dp[0][0]=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<k;j++)
		{
			dp[i][(j+a[i])%k]=max(dp[i-1][(j+a[i])%k],dp[i-1][j]+a[i]);
		}
	}
	if(dp[n][0]>0) cout << dp[n][0];
    else cout << -1;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int t=1;
	//cin >> t;

	while(t--)
	{
		solve();
	}
	return 0;
}