疑难杂题笔记——倍数问题

学习来源：https://www.acwing.com/video/795/

题目

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

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

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

数据保证一定有解。

输入格式

第一行包括 2 个正整数 n, K。

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

输出格式

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

数据范围

1≤n≤105,
1≤K≤103,
给定的 n 个数均不超过 108

输入样例：

4 3
1 2 3 4

输出样例：

9

思路

背包的常见套路

一般状态表示的时候，把限制放到维数里面，一般有几个限制，就用几维的状态表示。

朴素解法

（存在问题，大约可以过掉8个数据，时间复杂度大）

背包解法（一堆集合，从里面选出来一定量的东西，然后在满足一定的条件下，求一个最优解的问题）

优化

可以把其中的一些数字给抹掉
因为所有取模k 得到的一样的数，可以当作一个集合来看，都是等价的；
所以说可以取最大的三个来代表 这个集合里面的数；

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>

using namespace std;

const int N = 1010;
vector<int> a[N];  //用来存放余数一样的数字的集合
int n,m;
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 && u < a[i].size();u++)  //遍历灭一个集合的最大值
        {
            int x = a[i][u];
            for(int j = 3;j > 0;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;
 
}