解题思路:
注意事项:
参考代码:
#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;
}
0.0分
1 人评分
最小公倍数 (C语言代码)浏览:866 |
WU-字符串比较 (C++代码)浏览:767 |
C语言程序设计教程(第三版)课后习题10.4 (C语言代码)浏览:903 |
1009题解浏览:759 |
C语言程序设计教程(第三版)课后习题10.1 (C语言代码)浏览:570 |
A+B for Input-Output Practice (IV) (C语言代码)浏览:496 |
C语言程序设计教程(第三版)课后习题9.6 (C语言代码)浏览:589 |
2003年秋浙江省计算机等级考试二级C 编程题(1) (C语言代码)浏览:531 |
C二级辅导-公约公倍 (C语言代码)浏览:492 |
找出最长的字符串来 (C语言代码)浏览:1790 |