首页 > 试题广场 >

打 怪 兽

[编程题]打 怪 兽
  • 热度指数:756 时间限制:C/C++ 5秒,其他语言10秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
开始时你的能力是0,你的目标是从0号怪兽开始,通过所有的怪兽。
如果你当前的能力,小于i号怪兽的能力,你必须付出money[i]的钱,贿赂这个怪兽,然后怪兽就会加入你,他的能力直接累加到你的能力上;如果你当前的能力,大于等于i号怪兽的能力,你可以选择直接通过,你的能力并不会下降,你也可以选择贿赂这个怪兽,然后怪兽就会加入你,他的能力直接累加到你的能力上。
返回通过所有的怪兽,需要花的最小钱数。


输入描述:
第一行输入一个整数N,表示你的能力值N<=500
接下来N行,每行输入两个整数,表示怪兽的力量和需要的金钱


输出描述:
输出一个整数,需要花的最小钱数
示例1

输入

2
8 10
6 5

输出

10
public static long func(int[] power, int[] cost) {
    int len = power.length;
    int costSum = 0;
    for (int num : cost) {
        costSum += num;
    }
    // dp[i][j]含义:
    // 能经过0~i的怪兽,且花钱为j(花钱的严格等于j)时的武力值最大是多少?
    // 如果dp[i][j]==-1,表示经过0~i的怪兽,花钱为j是无法通过的,或者之前的钱怎么组合也得不到正好为j的钱数
    int[][] dp = new int[len][costSum + 1];
    // 第一行
    Arrays.fill(dp[0], -1);
    // 经过0~i的怪兽,花钱数一定为cost[0],达到武力值power[0]的地步。其他第0行的状态一律是无效的
    dp[0][cost[0]] = power[0];
    // 第一列
    for (int row = 1; row < len; row++) {
        dp[row][0] = -1;
    }

    for (int i = 1; i < len; i++) {  // 到第几号怪兽
        for (int j = 1; j < costSum + 1; j++) { // 正好花的钱数
            dp[i][j] = -1;
            // 可能性一,为当前怪兽花钱
            // 存在条件:
            // j - p[i]要不越界,并且在钱数为j - cost[i]时,要能通过0~i-1的怪兽,并且钱数组合是有效的。
            if (j >= cost[i] && dp[i - 1][j - cost[i]] != -1) {
                dp[i][j] = power[i] + dp[i - 1][j - cost[i]];
            }
            // 可能性二,不为当前怪兽花钱
            // 存在条件:
            // 0~i-1怪兽在花钱为j的情况下,能保证通过当前i位置的怪兽
            if (dp[i - 1][j] >= power[i]) {
                // 两种可能性中,选武力值最大的
                dp[i][j] = Math.max(dp[i][j], dp[i - 1][j]);
            }
        }
    }
    int ans = 0;
    // dp表最后一行上,dp[N-1][j]代表:
    // 能经过0~N-1的怪兽,且花钱为j(花钱的严格等于j)时的武力值最大是多少?
    // 那么最后一行上,最左侧的不为-1的列数(j),就是答案
    for (int j = 1; j < costSum + 1; j++) {
        if (dp[len - 1][j] != -1) {
            ans = j;
            break;
        }
    }
    return ans;
}

发表于 2022-02-05 16:13:50 回复(0)
帮我看看哪里错了,兄弟们
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int [] d=new int[n];
        int [] p=new int[n];
        scanner.nextLine();
        for (int i = 0; i < n; i++) {
            String s = scanner.nextLine();
            String[] s1 = s.split(" ");
            d[i]=Integer.parseInt(s1[0]);
            p[i]=Integer.parseInt(s1[1]);
        }
        //d 力量 p 金钱
        System.out.println(process(d,p,n,0));
    }

    public static int process(int [] d,int[] p,int hp,int index){
        if (index==d.length) return 0;
        if (hp<d[index]){
            return p[index]+process(d,p,hp+d[index],index+1);
        }else {
            return Math.min(p[index]+process(d,p,hp+d[index],index+1),process(d,p,hp,index+1));
        }
    }
}

发表于 2021-05-14 21:26:02 回复(1)