题解 | #购物单#
购物单
https://www.nowcoder.com/practice/f9c6f980eeec43ef85be20755ddbeaf4
热评第一报空指针，改了改。用例通过11/12，应该是越界。。。
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息public class Main {public static void main(String[] args) {Scanner in=new Scanner(System.in);int N=in.nextInt();int m=in.nextInt();N=N/10;Goods[] goods=new Goods[m+1];for(int i=1;i<=m;i++){int v=in.nextInt();int p=in.nextInt();int q=in.nextInt();goods[i]=new Goods(v,p,q);}
}
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in=new Scanner(System.in);
int N=in.nextInt();
int m=in.nextInt();
N=N/10;
Goods[] goods=new Goods[m+1];
for(int i=1;i<=m;i++){
int v=in.nextInt();
int p=in.nextInt();
int q=in.nextInt();
goods[i]=new Goods(v,p,q);
}
for(int i=1;i<=m;i++){
int q=goods[i].q;
if(q>0){
if(goods[q].a1==0)
goods[q].setA1(i);
else
goods[q].setA2(i);
}
}
int[][]dp=new int[m+1][N+1];
for (int i=1;i<=m;i++){
//主件
int v=goods[i].v;
int myd=v*goods[i].p;
int v1=0,v2=0,v3=0;
int myd1=0,myd2=0,myd3=0;
//主件+附件1
if(goods[i].a1!=0){
v1=v+goods[goods[i].a1].v;
myd1=myd+(goods[goods[i].a1].v*goods[goods[i].a1].p);
}
//主件+附件2
if(goods[i].a2!=0){
v2=v+goods[goods[i].a2].v;
myd2=myd+(goods[goods[i].a2].v*goods[goods[i].a2].p);
}
//主件+附件1+附件2
if(goods[i].a1!=0&&goods[i].a2!=0){
v3=v+goods[goods[i].a1].v+goods[goods[i].a2].v;
myd3=myd+(goods[goods[i].a1].v*goods[goods[i].a1].p)+(goods[goods[i].a2].v*goods[goods[i].a2].p);
}
for (int j=1;j<=N;j++){
if(goods[i].q>0)
dp[i][j]=dp[i-1][j];
else {
if (j >= v)
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - v] + myd);
if (j >= v1)
dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - v1] + myd1);
if (j >= v2)
dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - v2] + myd2);
if (j >= v3)
dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - v3] + myd3);
}
}
}
System.out.println(dp[m][N]*10);
}
private static class Goods {
public int v;
public int p;
public int q;
public int a1;
public int a2;
public Goods(int v, int p, int q) {
this.v = v/10;
this.p = p;
this.q = q;
}
public void setA1(int a1) {
this.a1 = a1;
}
public void setA2(int a2) {
this.a2 = a2;
}
}
}
