题目描述
思路:—> 选择问题实际上是背包问题
状态表示:
f[i][j][k]
集合:从前i个数中选,选了j个数(j<=3),且和mod K的值为k的所有选法
属性:和的最大值
状态计算:
f[i][j][k]
1.不选第i件物品:f[i][j][k]=f[i-1][j][k];
2.选第i件物品:
(x+Ai)mod K=k —> x+Ai= k+pK —> x = k-Ai+pK —> x%K = (k-Ai)%K
所以f[i][j][k]=f[i-1][j-1][mod(k-Ai,K)]+Ai
注:c++中负数取模运算是负数,所以x%y可以写成(x%y+y)%y,这样就保证了不会出现负数
时间复杂度:i -> 1e5 j->[0,3] k->[0,1000) 1e5 * 4 *1000=4 * 1e8
用贪心优化:
由于我们是要求最大的三个数,当两个数%K的值相同,我们可以取大的,效果是一样的
所以我们用一个vector[HTML_REMOVED] a[m]来存mod m值为[0,m-1]的数,a[x%m].push_back(x);//这样就存了所有
%m相同的那些x,然后从大到小排个序,每次最多只用前三个
同时在计算时,01背包可以一维优化,去掉i这一个维度
样例
blablabla
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
vector<int> a[N];
int f[4][N];
int mod(int x,int y)
{
return (x%y+y)%y;
}
int main()
{
int n,m;
cin>>n>>m;
for(int i=0;i<n;i++)
{
int x;
cin>>x;
a[x%m].push_back(x);
}
memset(f,-0x3f,sizeof f);//求最大值,先初始化为-INF
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++)//选前3大的
{
int x=a[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][mod(k-x%m,m)]+x);
}
}
}
}
cout<<f[3][0]<<endl;
return 0;
}