MY博客

一. 题目

众所周知，小葱同学擅长计算，尤其擅长计算一个数是否是另外一个数的倍数。

但小葱只擅长两个数的情况，当有很多个数之后就会比较苦恼。

现在小葱给了你 n 个数，希望你从这 n 个数中找到三个数，使得这三个数的和是 K 的倍数，
且这个和最大。

数据保证一定有解。

输入格式
第一行包括 2 个正整数 n, K。

第二行 n 个正整数，代表给定的 n 个数。

输出格式
输出一行一个整数代表所求的和。

数据范围
1≤n≤10^5,
1≤K≤10^3,
给定的 n 个数均不超过 10^8

输入样例：
4 3
1 2 3 4

输出样例：
9

二. 思路

三. 代码

1.普通三维(WA)(O(3nm))

//加上滚动数组或者去掉一维，空间可过，但时间TLE
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e5+10, M=1010;

int n, m;
int a[N];
int f[N][5][M];

signed main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) scanf("%d", &a[i]);

    memset(f, -0x3f, sizeof f);
    for(int i=0;i<=n;i++) f[i][0][0]=0;

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

    int ans=-1;
    for(int i=1;i<=n;i++) ans=max(ans, f[i][3][0]);
    cout<<ans<<endl;
}

2.优化三维(AC)

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;
const int N=1010;//k最大是1000

int n, m;
vector<int> allr[N];//以模m余数是几分类
int f[3*N][4][N];//dp数组, 优化到最多3*m个数

signed main()
{
    cin>>n>>m;

    while(n--)
    {
        int x;
        scanf("%d", &x);
        allr[x%m].push_back(x);
    }

    memset(f, -0x3f, sizeof f);           //一共3*m个数
    for(int i=0;i<=3*m;i++) f[i][0][0]=0;//从前i个中选0个余数是0

    int cnt=0;//记录枚举到第几个数
    for(int i=0;i<m;i++)//0-m-1类
    {//从大到小排序
        sort(allr[i].begin(), allr[i].end(), greater<int>());

        for(int u=0;u<min(3, (int)allr[i].size());u++)//0-m-1类前三大的数
        {
            int v=allr[i][u];//当前数
            cnt++;//枚举到那个数加1
            for(int j=1;j<=3;j++)//枚举选了几个
                for(int k=0;k<m;k++)//枚举余数
                    f[cnt][j][k]=max(f[cnt-1][j][k], f[cnt-1][j-1][((k-v)%m+m)%m]+v);
        }
    }

    int ans=-1;//一共3*m个数
    for(int i=1;i<=3*m;i++) ans=max(ans, f[i][3][0]);//前i个数中选，选3个余数是0的最大值
    cout<<ans<<endl;
}

//滚动数组优化
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;
const int N=1010;//k最大是1000

int n, m;
vector<int> allr[N];//以模m余数是几分类
int f[3][4][N];//f[3*N][4][N];//dp数组, 优化到最多3*m个数

signed main()
{
    cin>>n>>m;

    while(n--)
    {
        int x;
        scanf("%d", &x);
        allr[x%m].push_back(x);
    }

    memset(f, -0x3f, sizeof f);           //一共3*m个数
    //for(int i=0;i<=3*m;i++) f[i][0][0]=0;//从前i个中选0个余数是0
    for(int i=0;i<3;i++) f[i][0][0]=0;

    int cnt=0;//记录枚举到第几个数
    for(int i=0;i<m;i++)//0-m-1类
    {//从大到小排序
        sort(allr[i].begin(), allr[i].end(), greater<int>());

        for(int u=0;u<min(3, (int)allr[i].size());u++)//0-m-1类前三大的数
        {
            int v=allr[i][u];//当前数
            cnt++;//枚举到那个数加1
            for(int j=1;j<=3;j++)//枚举选了几个
                for(int k=0;k<m;k++)//枚举余数
                    f[cnt&1][j][k]=max(f[(cnt-1)&1][j][k], f[(cnt-1)&1][j-1][((k-v)%m+m)%m]+v);
        }
    }

    int ans=-1;//一共3*m个数
    for(int i=1;i<3;i++) ans=max(ans, f[i&1][3][0]);//前i个数中选，选3个余数是0的最大值
    cout<<ans<<endl;
}

3.优化二维(AC)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int N=1010;

int n, m;
vector<int> allr[N];
int f[5][N];//可以优化成后两维，由于i层只用到了i-1层，j-1, 严格小于j，
//所以只需要让j从大到小枚举就可以优化成两维

signed main()
{
    cin>>n>>m;

    for(int i=0;i<n;i++)
    {
        int x;
        scanf("%d", &x);
        allr[x%m].push_back(x);//余数相同的数
    }

    memset(f, -0x3f, sizeof f);
    f[0][0]=0;//选0个数，模m余数是0，最大值为0，
    //但选0个数，模m余数不可能非0，所以设成-无穷

    for(int i=0;i<m;i++)
    {
        sort(allr[i].begin(), allr[i].end(), greater<int>());//前三大

        for(int u=0;u<3&&u<allr[i].size();u++)
        {
            int x=allr[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);
                  //原式：f[i][j][k]=max(f[i-1][j][k], 
                  //f[i-1][j-1][(k-a[i])%m])
                  //等价变形即为代码式子<-让j从大到小枚举即为等价变形
        }
    }

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