描述

给一个数组，要求从数组中选取一些数，使得这些数的和为$kk$的倍数且和最大

思路

• 类似于背包的一个题，设$dp[n][m]dp[n][m]$表示考虑前$nn$个数，选取的数对$kk$取模为$mm$的最大价值
• 转移方程为$dp[n][m]=dp[n-1][(m-a[n])\mathrm{\%}k]+a[n]dp[n][m]=dp[n-1][(m-a[n])\backslash \%k]+a[n]$
• 采用滚动数组节省内存

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=1e3+5;
ll dp[2][MAXN];
ll a[MAXN];
int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    int now=0,nxt=1;
    memset(dp[now],-1,sizeof(dp[now]));
    dp[now][0]=0;
    for(int i=1;i<=n;i++)
    {
        memcpy(dp[nxt],dp[now],sizeof(dp[now]));
        for(int j=0;j<k;j++)
            if(dp[now][j]>=0)
                dp[nxt][(j+a[i])%k]=max(dp[nxt][(j+a[i])%k],dp[now][j]+a[i]);
        now^=1;nxt^=1;
    }
    if(dp[now][0]!=0)
        printf("%lld\n",dp[now][0]);
    else
        puts("-1");
}

时间复杂度$O(nk)O(nk)$，空间复杂度$O(k)O(k)$