倍数问题

解法:组合选择问题-背包模型

均参考大佬题解

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 1010
using namespace std;

int n,m;
vector<int> a[N];
int f[4][N];

int main()
{
    scanf("%d%d",&n,&m);

    for(int i = 0;i < n;i ++)
    {
        int x;
        scanf("%d",&x);
        a[x%m].push_back(x);
    }

    memset(f,-0x3f,sizeof f);
    f[0][0] = 0;

    for(int i = 0;i < m;i ++)
    {
        sort(a[i].begin(),a[i].end());
        reverse(a[i].begin(),a[i].end());

        for(int u = 0;u < 3 && a[i].size();u ++)
        {
            int x = a[i][u];
            for(int j = 3;j >= 1;j --)
                for(int k = 0;k < m;k ++)
                    f[j][k] = max(f[j][k],f[j-1][(k-x%m+m)%m]+x);
        }
    }
    printf("%d\n",f[3][0]);

    return 0;
}