如果你觉得这篇题解对你有用,可以点点关注再走呗~
分析
组合问题的最优解问题
在一类物品中,选取物品进行组合,使得满足某个条件的最优解
实际上是背包问题。
闫氏DP分析法
状态表示:f[i][j][k]:
所有从i
件物品中,选了j
件物品且总和%K
的余数为k
的集合
属性:Max
状态计算:
划分–>找不同点–>选或不选第i
个数
(1)不选第i个物品
f[i][j][k]=f[i-1][j][k]
(2)选第i个物品
f[i][j][j]=f[i-1][j-1][(k-a[i])%k]
时间复杂度:O(10^5*4*1000)=O(4*10^8);
超过10^8
,会TLE。
发现只需考虑k
的数值,与3个数的和值无关。
我们要找到的是3个数mod k
的最大值
余数k
为1000,对于每种k
,只需保留最大的那3位数。
总共最多只需保留3000个数
4*3000*k=1.2*10^7
优化后时间复杂度:O(10^7)
Accode
import java.util.*;
public class Main{
static int n,m;
static int N=1010;
static int INF=0x3f3f3f3f;
static int [][]f=new int [4][N];
static LinkedList []a=new LinkedList[N];
public static int mod(int x,int y) {
return (x%y+y)%y;
}
public static void main(String []args) {
Scanner sc=new Scanner(System.in);
n=sc.nextInt();
m=sc.nextInt();
for(int i=0;i<=m;i++) {
a[i]=new LinkedList<Integer>();
}
for(int i=1;i<=n;i++) {
int x=sc.nextInt();
a[x%m].add(x);
}
for(int i=0;i<=3;i++)Arrays.fill(f[i],-INF );
f[0][0]=0;
for(int i=0;i<=m;i++) {
Collections.sort(a[i]);
Collections.reverse(a[i]);
for(int u=0;u<Math.min(3,a[i].size());u++) {
int x= (int )a[i].get(u);
for(int j=3;j>=1;j--) {
for(int k=0;k<m;k++)
f[j][k]=Math.max(f[j][k],f[j-1][mod(k-x,m)]+x);
}
}
}
System.out.println(f[3][0]);
}
}
暴力
直接去枚举,i,j,k
三维的枚举
10^5*10^5*10^5=10^15
远远大于计算的时间复杂度
考试时优化不出来可取!
暴力(过了 6/13个数据)
import java.util.*;
public class Main{
static int a[]=new int [100010];
public static void main(String []args){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int K=sc.nextInt();
for(int i=1;i<=n;i++)a[i]=sc.nextInt();
long res=-0x3f3f3f;
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
for(int k=j+1;k<=n;k++){
if((a[i]+a[j]+a[k])%K==0){
res=Math.max(a[i]+a[j]+a[k],res);
}
}
}
}
System.out.println(res);
}
}