蓝桥杯2018年第九届真题-倍数问题（滚动数组）

解题思路:

注意事项:

参考代码:

#include<iostream>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<vector>

using namespace std;

#define LL long long

const int N=1e5+9;

int n,k;

int f[4][N],g[4][N];//滚动数组

vector <int> a[N];

int main()

{

    cin>>n>>k;

    for(int i=1;i<=n;i++)

    {

        int x;

        cin>>x;

        a[x%k].push_back(x);

    }

    memset(f,-1,sizeof(f));

    memset(g,-1,sizeof(g));

    for(int i=0;i<k;i++)

    {

        if(a[i].size()==0)

            continue;//没有对应的余数就跳过

        sort(a[i].begin(),a[i].end());

        reverse(a[i].begin(),a[i].end());

        int len=a[i].size();

        //取余数相同的比较大的几个（3个）

        for(int j=0;j<min(3,len);j++)

        {

            int x=a[i][j];//可能会选到的数x;

            g[1][i]=max(f[1][i],x);

            for(int p=1;p<=2;p++)//枚举数的个数逐渐增加时，最大的和

            {

                for(int v=0;v<k;v++)

                {

                    if(f[p][v]!=-1)

                        g[p+1][(v+x)%k]=max(g[p+1][(v+x)%k],f[p][v]+x);

                }

            }

            for(int p=1;p<=3;p++)

            {

                for(int v=0;v<k;v++)

                {

                    f[p][v]=g[p][v];//复制回f数组

                }

            }

        }

    }

    cout<<g[3][0];

    return 0;

}