1、题目描述
小Q打算穿越怪兽谷，他不会打怪，但是他有钱。
他知道，只要给怪兽一定的金币，怪兽就会一直护送着他出谷。
在谷中，他会依次遇见N只怪兽，每只怪兽都有自己的武力值和要“贿赂”它所需的金币数。
如果小Q没有“贿赂”某只怪兽，而这只怪兽“武力值”又大于护送他的怪兽武力之和，这只怪兽就会攻击他。
小Q想知道，要想成功穿越怪兽谷而不被攻击，他最少要准备多少金币。
输入格式
第一行包含整数N，表示怪兽的数量。
第二行包含N个整数d1,d2,…,dnd1,d2,…,dn，表示每只怪兽的武力值。
第三行包含N个整数p1,p2,…,pnp1,p2,…,pn，表示收买N只怪兽所需的金币数。
输出格式
输出一个整数，表示所需最小金币数。
数据范围
1≤N≤501≤N≤50, 1≤di≤10121≤di≤1012, 1≤pi≤21≤pi≤2
输入样例1：
3 8 5 10 1 1 2输出样例1：
2输入样例2：
4 1 2 4 8 1 2 1 2输出样例2：
62、分析 - 动态规划
3、代码
import java.io.*; import java.util.*; public class Main{ static int N = 55, M = N * 2; static long[] d = new long[N]; //武力值 static int[] p = new int[N]; //金币，每个怪兽所花的金币数为1或2 static long[][] f = new long[N][M]; //long i个怪兽，花费的金币最少为j，获得的最大武力值 public static void main(String[] args) { Scanner in = new Scanner(new BufferedInputStream(System.in)); int n = in.nextInt(); for(int i = 1;i <= n;i ++) { d[i] = in.nextLong(); //int 最大 2*10^9 } for(int i = 1;i <= n;i ++) p[i] = in.nextInt(); //初始化 for(int i = 1;i < N;i ++) { Arrays.fill(f[i], -1); } f[0][0] = 0; for(int i = 1;i <= n;i ++) { for(int j = 1;j <= n*2;j ++) { if(j >= p[i] && f[i-1][j-p[i]] != -1) { f[i][j] = f[i-1][j-p[i]] + d[i]; //收买第i只，那么就需要保证前i-1个花的金币最少 }if(f[i-1][j] != -1 && f[i-1][j] >= d[i]) { f[i][j] = Math.max(f[i][j], f[i-1][j]); } } } //最后，找到第一个成功通过n个点的数 int res = 0; for(int i = 1;i <= n*2;i ++) { if(f[n][i] != -1) { res = i; break; } } System.out.println(res); } }
