题解 | #购物单#

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            String str = in.nextLine();
            String[] strings = str.split(" ");
            int Max_money = Integer.parseInt(strings[0]);
            int Max_count = Integer.parseInt(strings[1]);
            int[][] ss = new int[Max_count+1][5];
            for (int i = 1; i <= Max_count; i++) {
                String shop = in.nextLine();
                String[] shop1 = shop.split(" ");
                ss[i][0] = Integer.parseInt(shop1[0]);
                ss[i][1] = Integer.parseInt(shop1[1]) * Integer.parseInt(shop1[0]);
                ss[i][2] = Integer.parseInt(shop1[2]);
                int pan = ss[i][2];
                if (pan != 0) {
                    if (ss[pan][3] == 0) ss[pan][3] = i;
                    else ss[pan][4] = i;
                }
            }
            int[][] dp = new int[Max_count + 1][Max_money + 1];
            for (int i = 1; i <= Max_count; i++) {
                int v = ss[i][0];
                int p = ss[i][1];
                int q = ss[i][2];
                int f1 = ss[i][3];
                int f2 = ss[i][4];

                for (int j = 1; j <= Max_money; j++) {
                        dp[i][j] = dp[i - 1][j]; 
                        if (q != 0) continue;    
                        if (j >= v) {     
                            dp[i][j] = Math.max(dp[i][j],
                                                p + dp[i - 1][j - v]); 
                            if (f1 != 0 && j>=v+ss[f1][0]) dp[i][j] = Math.max(dp[i][j],
                                                                 p + ss[f1][1] + dp[i - 1][j - v - ss[f1][0]]);
                            if (f2 != 0 && j>=v+ss[f2][0]) dp[i][j] = Math.max(dp[i][j], p + ss[f2][1] + dp[i - 1][j - v - ss[f2][0]]);
                            if(f2 != 0 && j>=v+ss[f1][0]+ss[f2][0]) dp[i][j] = Math.max(dp[i][j],
                                                    p + ss[f1][1] + ss[f2][1] + dp[i - 1][j - v - ss[f1][0] - ss[f2][0]]);
                            
                        }
                    
                }
            }
            System.out.println(dp[Max_count][Max_money]);
        }
    }
}