原题链接

考察:背包dp

思路:

        组合问题一般用背包dp解决.f[i][j][k]表示前i个数选j个数,余数为k的最大和. 很容易想到状态转移方程f[i][j][k] = f[i-1][j-1][Get_Mod(k-a[i],K)]+a[i],f[i-1][j][k]之间取最值.时间复杂度是10⁵*10³*3 只能过8个数据.此时需要考虑一些优化.

        根据题意,不管n多大,最终都是只选3个数.而根据状态转移方程可以发现,f数组转移只与a[i]和a[i]的余数有关.假设当前j=2,Get_Mod(k-a[i],K) = t,那么不管a[i]多大,我们都只要选择能+t%k==0的a[i]即可.因此对于每种余数,我们只需要存储最大的3个a[i].时间复杂度优化到O(10³*3*10³*3)

        但是注意初始化的问题.可以发现f[i][0][1~K-1]明显是不合法的状态,所以需要memset去除不合法的状态.这里因为只需要i-1和i,所以可以优化到二维.

 1 #include <iostream>
 2 #include <cstring>
 3 #include <vector>
 4 #include <algorithm>
 5 using namespace std;
 6 const int N = 100010,M = 1000;
 7 int a[N],K,n,f[4][M],nums[M*3+10],cnt;
 8 vector<int> v[M];
 9 struct cmp{
10     bool operator()(int x,int y){
11         return x>y;
12     }
13 };
14 int Get_Mod(int x,int Mod)
15 {
16     return (x%Mod+Mod)%Mod;
17 }
18 int maxx(int a,int b)
19 {
20     return a>b?a:b;
21 }
22 int main()
23 {
24     scanf("%d%d",&n,&K);
25     for(int i=1;i<=n;i++)
26     {
27         scanf("%d",&a[i]);
28         v[Get_Mod(a[i],K)].push_back(a[i]);
29     }
30     for(int i=0;i<1000;i++)
31        if(v[i].size()) sort(v[i].begin(),v[i].end(),cmp());
32     for(int i=0;i<1000;i++)
33        for(int j=0;j<3&&j<v[i].size();j++)
34          nums[++cnt] = v[i][j];
35     memset(f,-0x3f,sizeof f);
36     f[0][0] = 0;
37     for(int i=1;i<=cnt;i++)
38     {
39         for(int j=3;j>=1;j--)
40           for(int k=0;k<K;k++)
41             f[j][k] = maxx(f[j-1][Get_Mod(k-nums[i],K)]+nums[i],f[j][k]);
42     }
43     printf("%d\n",f[3][0]);
44     return 0;
45 }