题解 | #购物单#

import java.util.*;
import java.util.stream.Collectors;
import java.util.concurrent.atomic.AtomicInteger;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int money = in.nextInt()/10;
        int productNum = in.nextInt();
        int[][] productValue = new int[productNum+1][3];
        int[][] productPrices = new int[productNum+1][3];
        for(int i=1; i<productNum+1; i++){
            int productPrice = in.nextInt()/10;
            int value = in.nextInt() * productPrice;
            int parentId = in.nextInt();
            if(parentId == 0 ){
                productValue[i][0] = value;
                productPrices[i][0] = productPrice;
            } else {
                if(productValue[parentId][1] == 0 ){
                    productValue[parentId][1] = value;
                    productPrices[parentId][1] = productPrice;
                }else{
                    productValue[parentId][2] = value;
                    productPrices[parentId][2] = productPrice;
                }
            }
        }
        int[][] results = new int[productNum+1][money+1];
        for(int i=1; i<productNum+1; i++){
            for(int j=1; j < money+1;j++){
                int priceOne = productPrices[i][0];
                int priceTwo = productPrices[i][1];
                int priceThree = productPrices[i][2];
                if(productPrices[i][0] <= 0){
                    results[i][j] = results[i-1][j];
                }
                if(productPrices[i][0] > j){
                    results[i][j] = results[i-1][j];
                } else {
                    if(j >= priceOne){
                        results[i][j] = Math.max(results[i-1][j],results[i-1][j-priceOne]+productValue[i][0]);
                    }
                    if(j >= (priceOne + priceTwo)){
                        results[i][j] = Math.max(results[i][j],results[i-1][j-priceTwo-priceOne] + productValue[i][0] + productValue[i][1]);
                    }
                    if(j >= (priceOne + priceThree)){
                        results[i][j] = Math.max(results[i][j],results[i-1][j-priceThree-priceOne] + productValue[i][0] + productValue[i][2]);
                    }
                    if(j >= (priceOne + priceTwo + priceThree)){
                        results[i][j] = Math.max(results[i][j],results[i-1][j-priceTwo-priceOne-priceThree] + productValue[i][0] + productValue[i][1] +  productValue[i][2]);
                    }
                }
            }
        }
        System.out.println(results[productNum][money]*10);
    }

}