题解 | #购物单#

public static void main(String[] args) {
    Scanner ac = new Scanner(System.in);
    int N = ac.nextInt() / 10;
    if(N >= 3200){
        return;
    }
    int m = ac.nextInt();
    if(m >= 60){
        return;
    }
    Goods[] goodsArr = new Goods[m+1];
    goodsArr[0] = new Goods(0,0,0); //控制初始化
    for(int i = 1; i <= m; i++){
        int v = ac.nextInt() / 10; //价格
        int p = ac.nextInt(); //重要度
        int q = ac.nextInt(); //标识
        Goods goods = new Goods(v,v*p,q);
        goodsArr[i] = goods;
    }
    for(Goods goods : goodsArr){
        if(goods.q != 0){
            //附件
            if(goodsArr[goods.q].fGoodsArr[0] == null){
                goodsArr[goods.q].fGoodsArr[0] = goods;
            }else{
                goodsArr[goods.q].fGoodsArr[1] = goods;
            }
        }
    }

    int[][] dp = new int[m+1][N+1];
    for(int i = 1;i <= m;i++){ //从1 开始 默认 int[0][j] = 0,意义就是一个物品也不放 满意度就是0
        for(int j = 1; j <= N; j++){ //同上，默认int[i][0] = 0,意义就是一分钱也没有，满意度就是0
            Goods curGoods = goodsArr[i];
            if(curGoods.q == 0){ //钱够买第i个物品 并且是主件
                if(j >= curGoods.price){
                    //如要买，这是满意度，其中 dp[i-1][j-curGoods.price] 这个的意义是总钱数减去当前物品的钱数，能够购买i-1个物品的最大满意度
                    //比如我有1000 快需要再买一个400块的东西，满意度应该是 600块能够购买的最大满意度减伤当前物品的满意度， 动态规划 600的已经算过了 直接拿来用
                    int myd = dp[i-1][j-curGoods.price]+curGoods.myd;
                    dp[i][j] = Math.max(dp[i-1][j],myd);
                }

                if(curGoods.fGoodsArr[0] != null && i >= 2){
                    //有附件
                    int price = curGoods.price + curGoods.fGoodsArr[0].price; //总价格
                    if(j >= price){  //钱够
                        dp[i][j] = Math.max(dp[i-1][j],dp[i-2][j-price]+ curGoods.myd+ curGoods.fGoodsArr[0].myd); //得拿出两个物品
                    }
                    if(curGoods.fGoodsArr[1] != null){
                        price = curGoods.price + curGoods.fGoodsArr[1].price;
                        if(j >= price){
                            dp[i][j] = Math.max(dp[i-1][j],dp[i-2][j-price]+ curGoods.myd+ curGoods.fGoodsArr[1].myd);
                        }
                        if(i >=3){
                            price = curGoods.price + curGoods.fGoodsArr[0].price + curGoods.fGoodsArr[1].price;
                            if(j >= price){
                                dp[i][j] = Math.max(dp[i-1][j],dp[i-3][j-price]+ curGoods.myd + curGoods.fGoodsArr[0].myd + curGoods.fGoodsArr[1].myd); //得拿出三个物品
                            }
                        }
                    }
                }
            }
        }
    }
    System.out.println(dp[m][N]*10);
}

static class Goods{
    int price;
    int myd;
    int q;
    Goods[] fGoodsArr = new Goods[2];
    public Goods(int price,int myd,int q){
        this.price = price;
        this.myd = myd;
        this.q = q;
    }
}