题解 | #购物单#

这道题典型的思路简单，实现复杂

import java.util.*;
public class Main {
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int money = in.nextInt();
        int num = in.nextInt();
        int[][] shoppingList = new int[num][3];
        for (int i = 0; i < num; i++) {
            for (int j = 0; j < 3; j++) {
                shoppingList[i][j] = in.nextInt();
            }
        }
        System.out.println(maxSatisfaction(money, num, shoppingList));
    }
    public static int maxSatisfaction(int money, int num, int[][] shoppingList) {
        //由于物品都是10的整数倍，因此可以使用dp
        int[][] dp = new int[num + 1][money / 10 + 1];
        //主件满意度,主件加附件1，主件加附件2，主件加附件1和2，附件一价格，附件二价格。
        int[][] values = getValues(shoppingList);
        for (int i = 1; i <= num; i++) {
            for (int j = 1; j < dp[0].length; j++) {
                if (shoppingList[i - 1][2] == 0) {  //是主件
                    //主件价格,满意度
                    int a = shoppingList[i - 1][0], b = values[i - 1][0];
                    //主件附件1价格，满意度
                    int c = values[i - 1][4], d = values[i - 1][1];
                    //主件附件2价格，满意度
                    int e = values[i - 1][5], f = values[i - 1][2];
                    //买主件还是不买
                    if (10 * j >= a) dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - a / 10] + b);
                    else dp[i][j] = dp[i - 1][j];
                    //买主件1还是保持
                    if (10 * j >= a + c) dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - (a + c) / 10] + b + d);
                    //买主件2还是保持
                    if (10 * j >= a + e) dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - (a + e) / 10] + b + f);
                    //买全部还是保持
                    if (10 * j >= a + c + e) dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - (a + c + e) / 10] + b + d + f);
                } else dp[i][j] = dp[i - 1][j];
            }
        }
        return dp[num][dp[0].length - 1];
    }
    //生成价值矩阵
    public static int[][] getValues(int[][] shoppingList) {
        //主件满意度,主件加附件1，主件加附件2，主件加附件1和2，附件一价格，附件二价格，
        int[][] values = new int[shoppingList.length][6];
        for (int i = 0; i < values.length; i++) {
            if (shoppingList[i][2] == 0) {
                values[i][0] = shoppingList[i][0] * shoppingList[i][1];
            } else {
                if (values[shoppingList[i][2] - 1][1] == 0)
                    values[shoppingList[i][2] - 1][1] = shoppingList[i][0] * shoppingList[i][1];
                else values[shoppingList[i][2] - 1][2] = shoppingList[i][0] * shoppingList[i][1];
                if (values[shoppingList[i][2] - 1][4] == 0) values[shoppingList[i][2] - 1][4] = shoppingList[i][0];
                else values[shoppingList[i][2] - 1][5] = shoppingList[i][0];
            }
            values[i][3] = values[i][1] + values[i][2];
        }
        return values;
    } 
}