题目有点长,大意是说你有m种技能,每种技能的伤害是p[i],消耗水晶量为k[i];有n只怪兽,每只怪兽的生命值和防御力分别为a[i]和b[i]。每次释放技能怪兽的生命值会减少技能伤害减去怪兽防御力的差值 这道题乍看上去像是完全背包,因为每种技能可以重复施放,就像每种物品可以重复拿一样。但是我们发现防御力的数值范围是0到10,所以我们可以枚举防御力,这样就变成了个0-1背包,dpi的值表示杀掉一个生命值为i,防御力为j的怪物所需的最少晶石 那么对于每一种防御力i,枚举所有的生命值j(从1开始枚举),再枚举所有的技能l,如果这个技能一招刚好能打死这个怪物,就把dpj的值更新为min(dpj,k[l]);如果一招打不死,那么就把dpj的值更新为min(dpj,dp剩余血量 + k[l]) 最终答案即为:∑i dp[a[i]][b[i]]
import java.util.*;
public class Main {
static int n,m;//n只怪兽,m种技能
static int[] k = new int[1005];//第i种攻击方式消耗的晶石
static int[] p = new int[1005];//第i种攻击方式的伤害
static int[] a = new int[100005];//第i只怪兽的生命值
static int[] b = new int[100005];//第i只怪兽的防御力
static int[][] dp = new int[1005][11];
static int INF = 99999999;
//dp[i][j]的值表示杀掉一个生命值为i,防御力为j的怪物所需的最少晶石
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
while(cin.hasNext()) {
int max_a = 0,max_b = 0,max_p = 0;
n = cin.nextInt();
m = cin.nextInt();
for(int i = 1;i <= n;i++) {
String tmpa = cin.next();
String tmpb = cin.next();
a[i] = Integer.parseInt(tmpa);
b[i] = Integer.parseInt(tmpb);
max_a = Math.max(a[i],max_a);//记录最大的生命值
max_b = Math.max(b[i],max_b);//记录最大的防御力
}
for(int i = 1;i <= m;i++) {
String tmpk = cin.next();
String tmpp = cin.next();
k[i] = Integer.parseInt(tmpk);
p[i] = Integer.parseInt(tmpp);
max_p = Math.max(p[i],max_p);//记录最大的伤害
}
if(max_p <= max_b) {
System.out.println("-1");
continue;
}
for(int i = 0;i <= max_b;i++) {//枚举防御力
dp[0][i] = 0;//生命值为0的怪物所需的晶石为0
for(int j = 1;j <= max_a;j++) {//生命值
dp[j][i] = INF;
for(int l = 1;l <= m;l++) {//枚举所有的技能
if(p[l] > i) {
if(p[l] - i >= j)//能一招打死
dp[j][i] = Math.min(dp[j][i],k[l]);
else//一招打不死
dp[j][i] = Math.min(dp[j][i],dp[j - (p[l] - i)][i] + k[l]);
}
}
}
}
long ans = 0;
for(int i = 1;i <= n;i++)
ans += dp[a[i]][b[i]];
System.out.println(ans);
}
}
}
这个代码时间复杂度是O(10^7^),1s的时间复杂度大约是O(10^8^),所以过应该没问题 有的人可能不理解,为什么防御力和生命值都要依次枚举,万一并没有这个防御力的怪物或者没有这个生命值的怪物呢?假设就一只怪物,生命值为5,所有的技能都无法一招打死,假设剩下3血,那么这个时候dp5 = min(dp5,dp3 + k[l]),假如你对生命值进行了剪枝,因为怪物中并没有3血的,所以你不会去计算dp3,那这个时候就得不到正确答案。所以必须计算所有的生命值对应的防御力的最少水晶消耗量