题解 | #购物单#

import java.util.Scanner;
import java.util.*;

// 01背包 ，附件与主件绑定，两者合并可以看成另一件物品，通过预处理，整理成一堆新的物品
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int N = in.nextInt();
            int m = in.nextInt();
            int[] vs = new int[m];
            int[] ps = new int[m];
            int[] qs = new int[m];
            for(int i = 0; i < m; i++) {
                vs[i] = in.nextInt();
                ps[i] = in.nextInt();
                qs[i] = in.nextInt();
            }
            System.out.println(maxValue(N, vs, ps, qs));
        }
    }

    public static int maxValue(int n, int[] vs, int[] ps, int[] qs) {
        ArrayList<Item> items = new ArrayList<Item>();
        Item[] arr = new Item[vs.length];
	   //预处理
        for(int i = 0; i < vs.length; i++) {
            Item item = null;
            if(qs[i] == 0) {
                if(arr[i] != null) {
                    arr[i].setVal(vs[i],ps[i]);
                } else {
                    item = new Item(vs[i], ps[i], false);
                    arr[i] = item;
                }
            } else {
                if(arr[qs[i]-1] != null) {
                    arr[qs[i]-1].setSub(vs[i],ps[i]);
                } else {
                    if(qs[i]-1 <= i) {
                        arr[qs[i]-1].setSub(vs[i],ps[i]);
                    } else{
                        item = new Item(vs[i], ps[i], true);
                        arr[qs[i]-1] = item;
                    }
                }
            }
        }
        for(Item item : arr) {
            if(item != null) {
                items.add(item);
            }
        }
	    //背包和物品临界值加1 为了节省初始化步骤
        int[][] dp = new int[items.size()+1][n+1];
        for(int i = 1; i <= items.size(); i++) {
            for(int j = 0; j <= n; j++) {
                dp[i][j] = dp[i-1][j];
                if(j >= items.get(i-1).val) {
                    dp[i][j] = Math.max(dp[i][j], dp[i-1][j-items.get(i-1).val]
                            + items.get(i-1).val*items.get(i-1).p);
                }
                if(j >= items.get(i-1).val + items.get(i-1).sub1) {
                    dp[i][j] = Math.max(dp[i][j],
                            dp[i-1][j-items.get(i-1).val-items.get(i-1).sub1]
                                    + items.get(i-1).val*items.get(i-1).p
                                    + items.get(i-1).sub1p*items.get(i-1).sub1);
                }
                if(j >= items.get(i-1).val + items.get(i-1).sub2) {
                    dp[i][j] = Math.max(dp[i][j],
                            dp[i-1][j-items.get(i-1).val- items.get(i-1).sub2]
                                    +items.get(i-1).val*items.get(i-1).p
                                    +items.get(i-1).sub2*items.get(i-1).sub2p);
                }
                if(j >= items.get(i-1).val  + items.get(i-1).sub1 + items.get(i-1).sub2) {
                    dp[i][j] = Math.max(dp[i][j],
                            dp[i-1][j-items.get(i-1).val-items.get(i-1).sub1-items.get(i-1).sub2]
                                    +items.get(i-1).val*items.get(i-1).p
                                    +items.get(i-1).sub1*items.get(i-1).sub1p
                                    +items.get(i-1).sub2*items.get(i-1).sub2p);
                }
            }
        }
        return dp[items.size()][n];
    }

    public static class Item {
        int sub1;
        int sub1p;
        int sub2;
        int sub2p;
        int val;
        int p;
        public Item(int val, int p, boolean isSub) {
            if(isSub) {
                setSub(val, p);
            } else {
                this.val = val;
                this.p = p;
            }
        }
        private void setVal(int val, int p) {
            this.val = val;
            this.p = p;
        }
        private void setSub(int subval, int subp) {
            if(sub1 == 0) {
                sub1 = subval;
                sub1p = subp;
            } else {
                sub2 = subval;
                sub2p = subp;
            }
        }
    }
}