题解 | #购物单#

import java.util.Scanner;
import java.util.*;
import java.lang.Math;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {

    public static class Menu {
        public int v;
        public int p;
        public int q;
    }

    public static int getBase(int money) {
        int base = 1;
        while (money % 10 != 0 && money > 10) {
            money /= 10;
            base *= 10;
        }
        return base;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        //总钱数money
        int money = in.nextInt();

        //商品数量m
        int m = in.nextInt();

        int[][] prices = new int[m + 1][3];
        int[][] values = new int[m + 1][3];


        List<Menu> list = new ArrayList();
        int base = getBase(money);

        int[][] dp = new int[m + 1][(money / base) + 1];
        int number = m;

        while (number > 0) {
            int v = in.nextInt();
            int p = in.nextInt();
            int q = in.nextInt();

            Menu menu = new Menu();
            menu.v = v / base;
            menu.p = p;
            menu.q = q;

            list.add(menu);
            number--;
        }


        for (int i = 0; i < list.size(); i++) {
            if (list.get(i).q == 0) {
                prices[i + 1][0] = list.get(i).v;
                values[i + 1][0] = list.get(i).v * list.get(i).p;
            } else {
                int q = list.get(i).q;
                if (prices[q][1] == 0) {
                    prices[q][1] = list.get(i).v;
                    values[q][1] = list.get(i).v * list.get(i).p;
                } else {
                    prices[q][2] = list.get(i).v;
                    values[q][2] = list.get(i).v * list.get(i).p;
                }
            }
        }


        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= money / base; j++) {

                int price0 = prices[i][0];
                int price1 = prices[i][1];
                int price2 = prices[i][2];
                 
			    //这里做了一个优化，如果都是0的话，不需要处理
                if(price0 == 0 && price1 == 0 && price2 ==0){
                    dp[i][j] = dp[i - 1][j]; 
                    continue;
                }

                dp[i][j] = j - price0 >= 0 ? Math.max(dp[i - 1][j],
                                                      dp[i - 1][j - price0] + values[i][0]) : dp[i - 1][j];

                dp[i][j] = j - price0 - price1 >= 0 ? Math.max(dp[i][j],
                           dp[i - 1][j - price0 - price1] + values[i][0] +
                           values[i][1]) :  dp[i][j];

                dp[i][j] = j - price0 - price2 >= 0 ? Math.max(dp[i][j],
                           dp[i - 1][j - price0 - price2] + values[i][0] +
                           values[i][2]) :  dp[i][j];

                dp[i][j] = j - price0 - price1 - price2 >= 0 ? Math.max(
                               dp[i][j],
                               dp[i - 1][j - price0 - price1 - price2] + values[i][0] +
                               values[i][1] + values[i][2]) :  dp[i][j];
            }

        }

        System.out.println(dp[m][money / base] * base);





    }




}