沧海的孤塔

沧海的孤塔"/>

沧海的孤塔

沧海的孤塔-chimera --答案

时间复杂度为O(mn)

public class Main{public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int m = scanner.nextInt();int k = scanner.nextInt();long[] a = new long[n+1];for (int i = 1; i <= n; i++) {a[i] = scanner.nextInt();}//dptable[i][j]代表第i时刻发起j次攻击的话最大的总伤害值long[][] dptable = new long[n+1][m+1];LinkedList<Integer> q = new LinkedList<>();for (int i = 1; i <= n; i++) {dptable[i][0] = Long.MIN_VALUE;}dptable[0][0] = 0;for (int i = 1; i <= m; i++) {q.add(0);for (int j = 1; j <= n; j++) {while(!q.isEmpty()&&q.getFirst() < j - k) q.removeFirst();dptable[j][i] = dptable[q.getFirst()][i-1] + a[j];while(!q.isEmpty()&&dptable[q.getLast()][i-1] <= dptable[j][i-1]) q.removeLast();q.addLast(j);}q.clear();}long res = 0;for (int i = n; i > n - k; i--) {res = Math.max(res,dptable[i][m]);}System.out.println(res);}
}

时间复杂度为O(mnk)

public class Main{public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int m = scanner.nextInt();int k = scanner.nextInt();int[] array = new int[n+1];//dpatble[i][1][j]代表 第i时刻发起攻击且已经发起了j攻击的最大总伤害值//dpatble[i][0][j]代表 第i时刻不发起攻击且已经发起了j攻击的最大总伤害值long[][][] dptable = new long[n+1][2][m+1];for (int i = 1; i <= n; i++) {array[i] = scanner.nextInt();for (int j = 1; j <= i&&j<=m; j++) {long max = 0L;for(int ab= i-1;ab>=1&&ab>=i-k+1;ab--){max = Math.max(dptable[ab][1][j],max);}dptable[i][0][j] = max;if(i-k>=1){max = Math.max(max,dptable[i-k][1][j-1]);}if(i>k&&max==0) dptable[i][1][j] = 0;else dptable[i][1][j] =  max+array[i];}}System.out.println( Math.max(dptable[n][0][m],dptable[n][1][m]));}
}