解题思路:
注意事项:
参考代码:
#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语言程序设计教程(第三版)课后习题9.8 (Java代码)浏览:1636 |
C语言程序设计教程(第三版)课后习题11.5 (C语言代码)浏览:889 |
C语言程序设计教程(第三版)课后习题3.7 (C语言代码)浏览:326 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:520 |
1025题解浏览:733 |
1128题解(返回值为数组的情况)浏览:451 |
字符串比较 (C语言代码)浏览:680 |
数列有序 (C语言代码)浏览:930 |
C语言程序设计教程(第三版)课后习题8.4 (C语言代码)浏览:553 |
C语言程序设计教程(第三版)课后习题6.9 (C语言代码)浏览:479 |