如果你当前的能力,小于i号怪兽的能力,你必须付出money[i]的钱,贿赂这个怪兽,然后怪兽就会加入你,他的能力直接累加到你的能力上;如果你当前的能力,大于等于i号怪兽的能力,你可以选择直接通过,你的能力并不会下降,你也可以选择贿赂这个怪兽,然后怪兽就会加入你,他的能力直接累加到你的能力上。
返回通过所有的怪兽,需要花的最小钱数。
第一行输入一个整数N,表示你的能力值N<=500接下来N行,每行输入两个整数,表示怪兽的力量和需要的金钱
输出一个整数,需要花的最小钱数
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;
} 帮我看看哪里错了,兄弟们
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));
}
}
}