1234. 倍数问题
视频讲解
众所周知，小葱同学擅长计算，尤其擅长计算一个数是否是另外一个数的倍数。
但小葱只擅长两个数的情况，当有很多个数之后就会比较苦恼。
现在小葱给了你 n 个数，希望你从这 n 个数中找到三个数，使得这三个数的和是 K 的倍数，且这个和最大。
数据保证一定有解。
输入格式
第一行包括 2 个正整数 n,?K。
第二行 n 个正整数，代表给定的 n 个数。
输出格式
输出一行一个整数代表所求的和。
数据范围
1≤n≤105,
1≤K≤103,
给定的 n 个数均不超过 108
输入样例：
4 3
1 2 3 4
输出样例：
9
这道题很有难度，我之前做过类似的，我只想到了用余数怎么去搭配，其实y总说用dp 的时候我写了一个三维的，但是行不通，然后我仔细的去看了y总的优化，y总优化的确实很好很好，然后我也觉得这是dp中很好的一道题，建议看两遍y总的视频
最终代码如下：
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>using namespace std;const int N=1e5+10,M=1e3+10;vector<int> a[M];
int f[4][N];int get_id(int x,int n)
{
return (x%n+n)%n;
}
int main(void)
{
int n,k;cin>>n>>k;for(int i=1;i<=n;i++){
int t;cin>>t;a[t%k].push_back(t);}memset(f,-0x3f,sizeof f);f[0][0]=0;for(int i=0;i<k;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>=1;j--)for(int m=0;m<k;m++)f[j][m]=max(f[j-1][get_id(m-x,k)]+x,f[j][m]);}}cout<<f[3][0];
}