题解 | #合唱团#

HashMap为何改为尾插法

import java.util.;
import java.lang.;
public class Main{
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
while(scanner.hasNextInt()){
int n = scanner.nextInt();
int[] abilities = new int[n];
for(int i =0;i<n;i++){
abilities[i] = scanner.nextInt();
}
int k = scanner.nextInt();
int d = scanner.nextInt();
long res = getRes(n,abilities,k,d);
System.out.println(res);
}
}
public static long getRes(int n,int[] abilities,int k,int d){
if(k == 1){
long ans = Long.MIN_VALUE;
for(int i =0;i<abilities.length;i++){
if(abilities[i] > ans){
ans = abilities[i];
}
}
return ans;
}
long[][] dp = new long[n][k+1];
long[][] dp_min = new long[n][k+1];
for(int i =0;i<dp.length;i++){
Arrays.fill(dp[i],Long.MIN_VALUE);
Arrays.fill(dp_min[i],Long.MAX_VALUE);
}
for(int i =0;i<dp.length;i++){
dp[i][1] = abilities[i];
dp_min[i][1] = abilities[i];
}
long res = Long.MIN_VALUE;
for(int i =0;i<n;i++){
refreshDp(dp,dp_min,abilities,i,d);
res = Math.max(res,dp[i][k]);
}
return res;
}
public static void refreshDp(long[][] dp,long[][] dp_min,int[] abilities,int index ,int d){
for(int i = index-1;i>=index - d;i--){
if(i < 0){break;}
for(int k = 2;k<dp[1].length;k++){
if(abilities[index] >= 0){
if(dp[i][k-1] != Long.MIN_VALUE){
dp[index][k] = Math.max(dp[index][k],dp[index][1] * dp[i][k-1]);
}
if(dp_min[i][k-1] != Long.MAX_VALUE){
dp_min[index][k] = Math.min(dp_min[index][k],dp_min[index][1] * dp_min[i][k-1]);
}
}else{
if(dp_min[i][k-1] != Long.MAX_VALUE){
dp[index][k] = Math.max(dp[index][k],dp_min[index][1] * dp_min[i][k-1]);
}
if(dp[i][k-1] != Long.MIN_VALUE){
dp_min[index][k] = Math.min(dp_min[index][k],dp_min[index][1] * dp[i][k-1]);
}
}
}
}
}
}