题目链接：HDOJ6081
思路
题目大意是说，给你n个熊（那么他们编号默认就是1...n），然后给定m行输入，每一行都有u,v,w三个变量，表示u熊和v熊之间有强关系w，然后问你至少需要多少要付出多少代价，才能让他们之间有间隙
首先是有间隙是什么意思，并不是说要使整个图分成两部分，而是使得有一个独立的点，具体见下图：
只要有任意一个点变成孤立的点，即可达到要求。其次题目并没有说u,v只有一层强关系，就像上图一样，虚线表示他们还有第二层强关系。最后一个要注意的地方，就是u和v相等，题目并没有说u和v不相等，相等也就是自环，自己与自己有强关系，这个没有必要考虑，所以如果遇到u=v，我们不应该将其计入i熊的强关系
代码
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
while(cin.hasNext()) {
int n = cin.nextInt();
int[] sum = new int[n];//表示i号将领的总强关系值为sum[i-1]
for(int i = 0;i < n;i++)
sum[i] = 0;
int m = cin.nextInt();
for(int i = 0;i < m;i++) {
int u = cin.nextInt();
int v = cin.nextInt();
int w = cin.nextInt();
if(u == v)
continue;
sum[u - 1] += w;
sum[v - 1] += w;
}
Arrays.sort(sum);
System.out.println(sum[0]);
}
}
}题目链接：HDOJ6082
思路
题目有点长，大意是说你有m种技能，每种技能的伤害是p[i]，消耗水晶量为k[i]；有n只怪兽，每只怪兽的生命值和防御力分别为a[i]和b[i]。每次释放技能怪兽的生命值会减少技能伤害减去怪兽防御力的差值
这道题乍看上去像是完全背包，因为每种技能可以重复施放，就像每种物品可以重复拿一样。但是我们发现防御力的数值范围是0到10，所以我们可以枚举防御力，这样就变成了个0-1背包，dpi的值表示杀掉一个生命值为i，防御力为j的怪物所需的最少晶石
那么对于每一种防御力i，枚举所有的生命值j（从1开始枚举），再枚举所有的技能l，如果这个技能一招刚好能打死这个怪物，就把$dp[j][i]$的值更新为$min(dp[j][i],k[l])$；如果一招打不死，那么就把$dp[j][i]$的值更新为$min(dp[j][i],dp[剩余血量][防御力] + k[l])$
最终答案即为：$\sum_{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^1)$，1s的时间复杂度大约是$O(10^8)$，所以过应该没问题
有的人可能不理解，为什么防御力和生命值都要依次枚举，万一并没有这个防御力的怪物或者没有这个生命值的怪物呢？假设就一只怪物，生命值为5，所有的技能都无法一招打死，假设剩下3血，那么这个时候$dp[5][x] = min(dp[5][x],dp[3][x] + k[l])$，假如你对生命值进行了剪枝，因为怪物中并没有3血的，所以你不会去计算$dp[3][x]$，那这个时候就得不到正确答案。所以必须计算所有的生命值对应的防御力的最少水晶消耗量
题目链接：HDOJ6083
代码
package baidu;
import java.util.*;
public class Main {
static int B;//预算
static int N;//菜品数量
static int[] value = new int[1002];//菜品得分
static int[] money = new int[1002];//菜品价格
static int[][] result = new int[101][1002];
static int[] sta = new int[120];
static int top = 0,ans = 0;
static void print(int i,int wt) {
if(i == 1) {
if(result[i][wt] != 0) {
sta[top++] = 1;
ans += money[1];
}
return;
}
if(result[i][wt] > result[i - 1][wt]) {
print(i - 1,wt - money[i]);
sta[top++] = i;
ans += money[i];//如果选了，则打印编号
}
else
print(i - 1,wt);
}
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int t = cin.nextInt();
int sum = 0;
while((t--) != 0) {
for(int i = 0;i < 101;i++)
for(int j = 0;j < 1002;j++)
result[i][j] = 0;
top = ans = 0;
B = cin.nextInt();
N = cin.nextInt();
for(int i = 1;i <= N;i++) {
value[i] = cin.nextInt();
money[i] = cin.nextInt();
}
for(int i = 1;i <= N;i++) {
for(int j = 0;j <= B;j++) {
if(j < money[i])
result[i][j] = result[i - 1][j];
else
result[i][j] =
Math.max(result[i - 1][j],result[i - 1][j - money[i]] + value[i]);
}
}
if(N != 0)
print(N,B);
System.out.println("Case #" + ++sum + ":");
System.out.print(result[N][B] + " ");
System.out.println(ans);
if(0 < top)
System.out.print(sta[0]);
for(int i = 1; i < top; ++i)
System.out.print(" " +sta[i]);
if(top > 0)
System.out.println("");
}
}
}题目链接：HDOJ6084
