普适做法:会出现MLE和TLE
//f[i][j][k]:表示从前i个数中选j个,且j个数的和%K等于k的所有情况中j个数的和的最大值
import java.io.*;
import java.util.*;
public class Main{
static int N = 100010;
static int M = 1010;
static int[] w = new int[N];
static int[][] f = new int[4][M];
public static void main(String[] args)throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] s1 = br.readLine().split(" ");
int n = Integer.parseInt(s1[0]);
int K = Integer.parseInt(s1[1]);
String[] s2 = br.readLine().split(" ");
for(int i = 1; i <= n; i ++) w[i] = Integer.parseInt(s2[i - 1]);
//MLE:static int[][][] f = new int[N][4][M];
/*
for(int i = 1; i <= n; i ++) Arrays.fill(f[i], -0x3f3f3f3f);
for(int i = 1; i <= n; i ++) f[i][0][0] = 0;
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= 3; j ++){
for(int k = 0; k < K; k ++){
f[i][j][k] = f[i - 1][j][k];
f[i][j][k] = Math.max(f[i][j][k], f[i - 1][j - 1][(k - w[i] + K) % K] + w[i]);
}
}
}
System.out.println(f[n][3][0]);
*/
/*
优化数组大小从三维到二维:不会报MLT,会TLE,O(n*3*K)
通过了 9/13个数据
*/
for(int i = 0; i <= 3; i ++) Arrays.fill(f[i], -0x3f3f3f3f);
f[0][0] = 0;
for(int i = 1; i <= n; i ++){
for(int j = 3; j >= 1; j --){
for(int k = 0; k < K; k ++){
f[j][k] = Math.max(f[j][k], f[j - 1][((k - w[i]) % K + K) % K] + w[i]);
}
}
}
System.out.println(f[3][0]);
}
}
对第一层循环进行优化
优化思路:根据w[i]%K的值进行分组,最多有K组,每组取出最大的三个作为待选数(如果当前组中存在三个及以上个数)。
所要挑选的满足要求的三个数肯定取出的至多3K个待选数中,
即把第一层循环的n优化到了3K,最终时间复杂度O(n(3K3K))~10^7,可以过
import java.io.*;
import java.util.*;
public class Main{
static int N = 100010;
static int M = 1010;
static int[] w = new int[N];
static int[][] f = new int[4][M];
static List[] l = new List[M];
public static void main(String[] args)throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] s1 = br.readLine().split(" ");
int n = Integer.parseInt(s1[0]);
int K = Integer.parseInt(s1[1]);
String[] s2 = br.readLine().split(" ");
for(int i = 0; i < K; i ++){
l[i] = new ArrayList<Integer>();
}
for(int i = 1; i <= n; i ++){
w[i] = Integer.parseInt(s2[i - 1]);
l[w[i] % K].add(w[i]);
}
for(int i = 0; i <= 3; i ++) Arrays.fill(f[i], -0x3f3f3f3f);
f[0][0] = 0;
for(int t = 0; t < K; t ++){
Collections.sort(l[t]);
Collections.reverse(l[t]);
for(int i = 0; i < Math.min(3, l[t].size()); i ++){
for(int j = 3; j >= 1; j --){
for(int k = 0; k < K; k ++){
f[j][k] = Math.max(f[j][k], f[j - 1][((k - (int)l[t].get(i)) % K + K) % K] + (int)l[t].get(i));
}
}
}
}
System.out.println(f[3][0]);
}
}