MENU

2017百度之星资格赛

July 20, 2018 • Read: 301 • 算法

题目链接:HDOJ6081

image

思路

题目大意是说,给你n个熊(那么他们编号默认就是1...n),然后给定m行输入,每一行都有u,v,w三个变量,表示u熊和v熊之间有强关系w,然后问你至少需要多少要付出多少代价,才能让他们之间有间隙

首先是有间隙是什么意思,并不是说要使整个图分成两部分,而是使得有一个独立的点,具体见下图:

image
只要有任意一个点变成孤立的点,即可达到要求。其次题目并没有说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

image

思路

题目有点长,大意是说你有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

image

代码
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

image

题解

题解在这里!

最后编辑于: October 7, 2018
Archives Tip
QR Code for this page
Tipping QR Code