三道dp题龄的小太白的求助

P1064 [NOIP2006 提高组] 金明的预算方案

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

渣蛙牛逼


|