2017 百度之星资格赛

题目链接：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展开目录

题解展开目录

题解在这里！