题解 | #购物单#

import java.util.Scanner;

public class Main { static int N; static int m; static int[] v =new int[60]; static int[] p =new int[60]; static int[] q =new int[60]; static int[] v1 =new int[60]; static int[] p1 =new int[60]; static int[] q1 =new int[60]; static int s[][]=new int[60][3200];//满意度s[i][j]，表示从第i个物品看起，剩余10j钳的最大满意度。 static int count=0;//主件数量

public static void main(String[] args) {
    //输入
    Scanner sc = new Scanner(System.in);
    N=sc.nextInt();
    m=sc.nextInt();

    for (int i = 0; i < m; i++) {
        v[i]=sc.nextInt();
        p[i]=sc.nextInt();
        q[i]=sc.nextInt();
        if(q[i]==0) {
            count++;
        }
    }
    //动态规划解决最大满意度问题
    //最优子结构：
    //若（y1,...,yn)是最优解，(y2,...,yn)应该是相应子问题的最优解。
    //递归关系：
    //s[i][j]=(本就拿不了i，即v[i]>10j)s[i+1][j];
    //或者y[q[i]]==0,没拿主件。这里有问题，与范围外的数字相关了，因此需要数据预处理

    //预处理：将附件放在主件后，以便在不拿的时候连续的舍弃附件。
    //创建另一个相同大小的数组，遍历多次，选出主件填入后，将附件跟在其后，直到全部转移。
    boolean flag=true;//循环是否停止
    int dst=0;//是否在找附件，以及正在找的附件从属主件编号
    int mainPosition=0;//主件在新数组中的位置
    int j=0;//新数组的指针
    while (flag){
        flag=false;
        for (int i = 0; i < m; i++) {
            if (v[i]!=0)flag=true;
            if (dst!=0){
                if (q[i]==dst&&v[i]!=0){
                    insert(i,j, mainPosition+1);
                    j++;
                }
            }
            if (dst==0){
                if (q[i]==0&&v[i]!=0){
                    dst=i+1;
                    mainPosition=j;
                    insert(i,j);
                    j++;
                    i=-1;
                }
            }
        }
        dst=0;
    }

    //else （不拿i，且i为附件） s[i+1][j];
    //  (不拿i，且i为主件） s[i+x][j]
    //  (拿i) s[i+1][j-v[i]/10]+v[i]*p[i] 三者的最大值。
    //用备忘录方法求出s[0][N/10]
    int rs=result(0,N/10);
    System.out.println(rs);

    sc.close();
}

private static int result(int i, int j) {
    if (s[i][j]!=0)return s[i][j];
    if (i>=m-1){//走到最后一个物品
        if (v1[m-1]<=10*j){
            s[m-1][j]=v1[m-1]*p1[m-1];
        }
        else{
            s[m-1][j]=0;
        }
        return s[m-1][j];
    }
    if (v1[i]>10*j&&q1[i]!=0){
        s[i][j]=result(i+1,j);
        return s[i][j];//拿不了且为附件
    }
    if (v1[i]>10*j&&q1[i]==0){//拿不了且为主件
        int k=i+1;
        while(q1[k]==i+1){
            k++;
        }
        s[i][j]=result(k,j);
        return s[i][j];
    }
    //拿的了的2种情况
    if (q[i]==0){//是主件
        int k=i+1;
        while(q1[k]==i+1){
            k++;
        }
        s[i][j]=Math.max(result(k,j),result(i+1,j-v1[i]/10)+v1[i]*p1[i]);
        return s[i][j];
    }
    if(q[i]!=0){//是附件
        s[i][j]=Math.max(result(i+1,j),result(i+1,j-v1[i]/10)+v1[i]*p1[i]);
        return s[i][j];
    }
    return -1;
}

private static void insert(int i, int j) {
    v1[j]=v[i];
    p1[j]=p[i];
    q1[j]=0;
    v[i]=0;//标记为清空

}

//将原数组的i，插入到新数组的j的位置,并删除原元素
private static void insert(int i, int j,int mainPosition) {
    v1[j]=v[i];
    p1[j]=p[i];
    q1[j]=mainPosition;
    v[i]=0;//标记为清空
}

}