4418. 选元素

    思路：
    DP
    f[i][j]表示从前i个元素中选j个且第i个元素被选的最大元素和
    初始化：f[i][j] = -1e15, f[0][0] = 0
    状态转移：
    因为题目要求每k个元素一定有一个被选，故第i个元素被选，上一个被选的一定是p ∈Math.max(0, i - k), i - 1范围内
    f[i][j] = Math.max(f[i][j], f[p][j - 1] + a[i]
    结果：
    最后一个被选元素一定位于最后k个元素中，遍历找最大值

    1. import java.util.*;
    3. public class Main {
    4.     static final int N = 211;
    5.     static int[] a = new int[N];
    6.     static long[][] f = new long[N][N];
    7.     static int n, k, m;
    8.     public static void main(String[] args) {
    9.         Scanner sc = new Scanner(System.in);
    11.         n = sc.nextInt();
    12.         k = sc.nextInt();
    13.         m = sc.nextInt();
    15.         for (int i = 1; i <= n; i++)
    16.             a[i] = sc.nextInt();
    17.         for (int i = 0; i <= n; i++)
    18.             Arrays.fill(f[i], (long)(-1e15));
    19.         f[0][0] = 0;
    20.         for (int i = 1; i <= n; i++) {
    21.             for (int j = 1; j <= Math.min(i, m); j++) {
    22.                 for (int p = Math.max(0, i - k); p < i; p++)
    23.                         f[i][j] = Math.max(f[i][j], f[p][j - 1] + a[i]);
    24.             }
    25.         }
    27.         long ans = -1;
    28.         for (int i = Math.max(1, n - k + 1); i <= n; i++)
    29.             ans = Math.max(ans, f[i][m]);
    30.         System.out.println(ans);
    31.     }
    32. }