题解 | #购物单#

/*import java.util.*;
public class Main {
        public static void main(String[] args){
            Scanner sc = new Scanner(System.in);
            while(sc.hasNext()){
                int money= sc.nextInt();
                int nums = sc.nextInt();
                int[][] price = new int[nums+1][3];
                int[][] plusImportan = new int[nums+1][3];
                for(int i=0;i<nums;i++){
                        int v= sc.nextInt();
                        int p= sc.nextInt();
                        int q= sc.nextInt();
                    if(q==0){
                        //表示是主件
                        price[i][0]=v;
                        plusImportan[i][0]=v*p;
                    }else if(price[q][1]==0){
                        //表示是附件1,因为1当前的位置还是空的
                        price[q][1]=v;
                        plusImportan[q][1]=v*p;
                    }else{
                        //剩最后一种情况,附件2
                        price[q][2]=v;
                        plusImportan[q][2]=v*p;
                    }
                }
                //处理完了数据,接下来按照动态规划解法来写
                int[] dp = new int[money+1];//存总钱数
                for(int i=0;i<nums;i++){
                    if(price[i][0]==0){
                        //说明当前主件为空
                        continue;
                    }
                    for(int j=money;j>=price[i][0];j--){
                        int a =price[i][0];
                        int a1 = plusImportan[i][0];
                        int b =price[i][1];
                        int b1 = plusImportan[i][1];
                        int c =price[i][2];
                        int c1 = plusImportan[i][2];
                        if(j>=a){
                            //说明可以买下主件,那么刷新最大值,
                            dp[j]=Math.max(dp[j],dp[j-a]+a1);
                        }
                        if(j>=a+b){
                            //说明可以买下主件,那么刷新最大值,
                            dp[j]=Math.max(dp[j],dp[j-a-b]+a1+b1);
                        }
                        if(j>=a+c){
                            //说明可以买下主件,那么刷新最大值,
                            dp[j]=Math.max(dp[j],dp[j-a-c]+a1+c1);
                        }
                        if(j>=a+b+c){
                            //说明可以买下主件,那么刷新最大值,
                            dp[j]=Math.max(dp[j],dp[j-a-b-c]+a1+b1+c1);
                        }
                    }
                }
                System.out.println(dp[money]);
            }
        }
}*/
import java.util.*;
public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNextInt()){
            int money = sc.nextInt() / 10;// 输入目标金额
            int nums = sc.nextInt();// 输入循环次数,有多少件物品
            int[][] price = new int[nums + 1][3];// 用来存储主件 附件1 附件2 的价格
            int[][] plusImportan = new int[nums + 1][3];// 用来存储主件 附件1 附件2 的重要度（价格*重要度p）
            // 处理输入
            for(int i = 1;i <= nums;i++){
                int v = sc.nextInt() / 10;// 这个是主件价格
                int p = sc.nextInt();// 这个是输入的重要度
                int q = sc.nextInt();// 这个用来判断是主件还是附件，0是主件
                if(q == 0){
                    // 如果q为0，就是主件
                    price[i][0] = v;// 数组price的第1列为主键价格
                    plusImportan[i][0] = v * p;// plusImportant的第一列为价格 * 重要度
                }else if(price[q][1] == 0){
                    // 如果不是主件，并且第二列为空，那就写入第二列,写入第q个位置，而不是第i个位置了
                    price[q][1] = v;
                    plusImportan[q][1] = v * p;
                }else{
                    // 写入附件2的位置
                    price[q][2] = v;
                    plusImportan[q][2] = v * p;
                }
            }
 
            // 处理完输入数据，就完成动态规划
            int[] dp = new int[money + 1];// 转移方程: Max(dp[当前金额],dp[当前金额 - 待加入的金额] + 重要度])
            for(int i = 1;i <= nums; i++){
                if(price[i][0] == 0)// 当前主件为空
                    continue;// 继续循环
                for(int j = money; j >= price[i][0];j--){
                    // 从最大开始往前推，求出dp[money]的最优解
                    // 先将数据从数组中取出来
                    int a = price[i][0];
                    int a1 = plusImportan[i][0];
                    int b = price[i][1];
                    int b1 = plusImportan[i][1];
                    int c = price[i][2];
                    int c1 = plusImportan[i][2];
                    if (j >= a) {
                        // 如果能够买的下当前物品
                        dp[j] = Math.max(dp[j],dp[j - a] + a1);// 求解重要度
                    }
                    if(j >= a + b){
                        dp[j] = Math.max(dp[j],dp[j - a - b] + a1 + b1);// 求解重要度
                    }
                    if(j >= a + c){
                        dp[j] = Math.max(dp[j],dp[j - a  - c] + a1 + c1);// 求解重要度
                    }
                    if(j >= a + b + c){
                        dp[j] = Math.max(dp[j],dp[j - a - b - c] + a1 + b1 + c1);// 求解重要度
                    }
                }
            }
            System.out.println(dp[money] * 10);
    }
    }
}