hxqy1998 @ 2020-03-07 14:06:20
自我分析一下哈,应该是错在判断主件重复购买的问题,那能否标记每个f[i][j]处已经购买过的主件呢,不知各路大神见没见过这么奇葩的思路,还请帮帮小白。
附:10个点全部WA,每个测试点都比答案大。。。
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
int[] price = new int[m + 1];
int[] value = new int[m + 1];
int[] attachment = new int[m + 1];
for(int i = 1; i <= m; i++){
price[i] = in.nextInt();
value[i] = in.nextInt();
attachment[i] = in.nextInt();
}
int[][] f = new int[m + 1][n + 1];
boolean[][] buyMain = new boolean[m + 1][n + 1];
for(int i = 1; i <= m; i++){
for(int j = 1; j <= n; j++){
//压根买不起,走了
if(j < price[i]) {
f[i][j] = f[i-1][j];
}else{
//本身是主件,且之前没买过,抉择买不买这个主件
if(attachment[i] == 0 && !buyMain[i][j]) {
int buy = value[i] * price[i] + f[i - 1][j - price[i]];//买的价值
f[i][j] = Math.max(f[i - 1][j], buy);
//如果买的价值至少比不买价值高,买合适,为了以后买其附件做准备
if(buy >= f[i - 1][j]) buyMain[i][j] = true;
}else if(attachment[i] != 0){
//主件已买,只需抉择买不买附件
if(buyMain[attachment[i]][j]){
f[i][j] = Math.max(f[i - 1][j], value[i] * price[i] + f[i - 1][j - price[i]]);
}else{//主件没买,考虑主件附件一起买
if(price[attachment[i]] + price[i] > j){ //买不起二者,算了
f[i][j] = f[i-1][j];
}else {//能买得起,抉择:不买?俩一起买?
int buy = value[i]*price[i] + value[attachment[i]]*price[attachment[i]] + f[i - 1][j - price[i] - price[attachment[i]]];
f[i][j] = Math.max(f[i - 1][j], buy);
//如果买了主件,下次就不要再重复买了
if(buy >= f[i - 1][j]) buyMain[attachment[i]][j] = true;
}
}
}else{
//是主件,但前面买过了(这里是有问题吧)
f[i][j] = f[i-1][j];
}
}
}
}
System.out.println(f[m][n]);
}
}
by TRZ_2007 @ 2020-03-07 14:11:42
什么鬼语言
by pref_ctrl27 @ 2020-03-07 14:14:36
我不懂JAVA ,lz发个c++的吧
by Hemlix @ 2020-03-07 14:18:43
java好评啊
by 三废小霸王 @ 2020-07-10 13:46:13
渣蛙牛逼