AcWing 1234. 倍数问题(java)
原题链接
中等
作者:
mhb518340
,
2022-02-23 16:25:08
,
所有人可见
,
阅读 181
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Collections;
import java.util.Arrays;
public class Main{
static int N=1010;
static int INF=0x3f3f3f3f;
static int[][] f=new int[4][N];
static LinkedList[] a=new LinkedList[N];
public static void main(String args[]) throws IOException{
BufferedReader br=new BufferedReader(new InputStreamReader (System.in));
String[] s=br.readLine().split(" ");
int n=Integer.parseInt(s[0]);
int m=Integer.parseInt(s[1]);
for(int i=0;i<m;i++){
a[i]=new LinkedList<Integer>();
}
String[] ss=br.readLine().split(" ");
for(int i=1;i<=n;i++){
int x=Integer.parseInt(ss[i-1]);
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][(k-x%m+m)%m]+x);
}
}
System.out.println(f[3][0]);
}
}