题目描述

（a+b+c）%k =0
与 a、b、c 的值无关 , a、b、c可以被替代
例如 a%k==a1%k,那么a1 可以替代 a
所以我们应该关心 各数对 k的 余数。
余数相同的为一组，一组里面最多 选三个最大的数
为什么一组里面最多选三个：因为我们要在所有的数里面 找三个数：a b c，它们可能在同一组，也可能不在。

综上：问题 已转化为 01背包

三维

会内存超限

Code

#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
typedef long long ll;

const int N=1010;

vector<int> V[N];
ll  f[3*N][10][N];  // 从前i个数字里面选择， 且已经选了j个，且 和 mod K的余数为 k， 的最大值
int a[3*N];
int n,k;

int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        V[x%k].push_back(x);
    }

    int t=1;
    for(int i=0;i<k;i++)  // 余数为 i的 数组
      if(V[i].size()){   // no empty
         sort(V[i].begin(),V[i].end());
         reverse(V[i].begin(),V[i].end());
         for(int j=0;j<3&&j<V[i].size();j++)  a[t++]=V[i][j];
      }

    memset(f,-0x3f,sizeof f); // 该情况不存在，还没有选
    for(int i=1;i<=n;i++)  f[i][0][0]=0; // 该情况发生之后，就不再为负无穷，而是 为具体值了

    n=t-1;
    for(int i=1;i<=n;i++)
     for(int j=0;j<=3;j++)
      for(int u=0;u<k;u++){
       f[i][j][u]=f[i-1][j][u];
       if(j>=1) f[i][j][u]=max(f[i][j][u],f[i-1][j-1][((u-a[i])%k+k)%k]+a[i]);        
    }

    cout<<f[n][3][0];  
    return 0;
}

二维

滚动数组优化
AC！

Code

#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
typedef long long ll;

const int N=1010;

vector<int> V[N];
ll  f[10][N];  // 从前i个数字里面选择， 且已经选了j个，且 和 mod K的余数为 k， 的最大值
int a[3*N];
int n,k;

int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        V[x%k].push_back(x);
    }

    int t=1;
    for(int i=0;i<k;i++)  // 余数为 i的 数组
      if(V[i].size()){   // no empty
         sort(V[i].begin(),V[i].end());
         reverse(V[i].begin(),V[i].end());
         for(int j=0;j<3&&j<V[i].size();j++)  a[t++]=V[i][j];
      }

    memset(f,-0x3f,sizeof f); // 该情况不存在，还没有选
    f[0][0]=0; // 该情况发生之后，就不再为负无穷，而是 为具体值了

    n=t-1;
    for(int i=1;i<=n;i++)
     for(int j=3;j>=1;j--)
      for(int u=0;u<k;u++)
       f[j][u]=max(f[j][u],f[j-1][((u-a[i])%k+k)%k]+a[i]);        

    cout<<f[3][0];  
    return 0;
}