AcWing 1234. 倍数问题--DP的优化
原题链接
中等
作者:
LQstoic
,
2022-03-01 09:27:20
,
所有人可见
,
阅读 203
C++ 代码
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int N=1010;
vector<int>a[N];//本质:二维数组
int n,m;
int f[4][N];
int mod(int a,int b)
{
return (a%b+b)%b;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
int x;
scanf("%d",&x);
a[x%m].push_back(x);//二维数组
}
memset(f,-0x3f3f,sizeof f);
f[0][0]=0;//选0个数%k为0的最大数
for(int u=0;u<m;u++)//%k的余数,依次遍历所有数组
{
//从大到小排序
sort(a[u].begin(),a[u].end());
reverse(a[u].begin(),a[u].end());
for(int i=0;i<3 && i<a[u].size();i++)//只取每个数组的前三个
{
int x=a[u][i];
for(int j=3;j>=1;j--)
{
for(int k=0;k<m;k++)
{
//用u小时的f[j][k]去优化u大时的f[j][k]
f[j][k]=max(f[j][k],f[j-1][mod(k-x%m,m)]+x);
}
}
}
}
cout<<f[3][0]<<endl;
return 0;
}
大哥能解释下为什么选余数相同的前三个最大数吗
首先,选前三个保证这三个数之和是一定最大的
其次,选余数相同目的我认为是能够更好的划分集合的所有情况,因为%k余数相同的数的和%k的余数是不变的,如果选%k的余数不同的三个数相加,那情况就多了去了。当然,并不是说是k的倍数的最大三个数之和就是答案,也有可能%k余数不同的数刚好凑巧了,这么划分我们就可以用上述的状态转移方程很快去更新到底三个数之和最大是几。