动态规划(完全背包):费用报销

import java.util.ArrayList;
import java.util.Scanner;

/**
 * 费用报销 - 二维最大价值 DP（完全背包风格）
 *
 * 题意：选若干张发票报销，任意两张日期差 ≥ k 天，总金额不超过 m，求最大可报销金额。
 *
 * 状态定义：dp[i][j] = 只考虑到第 i 天（1..i）,在容量恰好为j的情况下,所能存的最大价值
 * 这道题的状态定义不一样,因为递推关系由i-k转移而来,
 *
 * 递推：
 * 1. 不选第 i 天任何票：dp[i][j] = dp[i-1][j]
 * 2. 选第 i 天的一张票 v：必须从“第 i-k 天及之前”的状态转移（保证与上一张间隔≥k），
 *    dp[i][j] = max(dp[i][j], dp[i-k][j-v] + v)，其中 j >= v
 * 3. 当 i < k 时，不能从“更早一天”转移，只能把“只选第 i 天一张 v”当作起点：dp[i][v] = max(dp[i][v], v)
 */
public class Main_Knapsack2D {
    static Scanner sc = new Scanner(System.in);
    static int[] pre = {0, 0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334};

    public static void main(String[] args) {
        int n = sc.nextInt();
        int m = sc.nextInt();
        int k = sc.nextInt();

        ArrayList<ArrayList<Integer>> a = new ArrayList<>();
        for (int i = 0; i <= 365; i++) a.add(new ArrayList<>());

        for (int i = 0; i < n; i++) {
            int mon = sc.nextInt();
            int d = sc.nextInt();
            int v = sc.nextInt();
            int day = pre[mon] + d;
            a.get(day).add(v);
        }

        int[][] dp = new int[366][m + 1];
        // dp[0][*] 已为 0，表示第 0 天、不选任何票时，任意容量下最大金额为 0

        for (int i = 1; i <= 365; i++) {
            // 先继承“不选第 i 天”的情况
            for (int j = 0; j <= m; j++) {
                dp[i][j] = dp[i - 1][j];
            }

            if (i >= k) {
                // 可以从第 i-k 天转移：选第 i 天的一张票 v，则 j 从 v 到 m，dp[i][j] = max(当前, dp[i-k][j-v]+v)
                for (int v : a.get(i)) {
                    for (int j = v; j <= m; j++) {
                        dp[i][j] = Math.max(dp[i][j], dp[i - k][j - v] + v);
                    }
                }
            } else {
                // 前 k 天内不能“接”在更早的票后面，只能单独选第 i 天的一张票
                for (int v : a.get(i)) {
                    if (v <= m) dp[i][v] = Math.max(dp[i][v], v);
                }
            }
        }

        // 容量维度不一定严格单调，这里安全起见在 0..m 中取最大值作为答案
        // 这也是为什么说,dp[i][j]是在前i天,容量恰好为j时的最大价值   
        int ans = 0;
        for (int j = 0; j <= m; j++) {
            if (dp[365][j] > ans) ans = dp[365][j];
        }
        System.out.println(ans);
        sc.close();
    }
}