如果你当前的能力,小于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)); } } }