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,如果这个技能一招刚好能打死这个怪物,就把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,那这个时候就得不到正确答案。所以必须计算所有的生命值对应的防御力的最少水晶消耗量

题目链接: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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏向治洪

ES7和ES8新特性介绍

概述 JavaScript,作为一门处于高速发展期的开发语言,正在变的越来越完善、稳定。我们必须拥抱这些变化,并且我们需要把ES8加入到我们的技术栈中。 ECM...

67460
来自专栏向治洪

浅谈前端JavaScript编程风格

前言 多家公司和组织已经公开了它们的风格规范,具体可参阅jscs.info,下面的内容主要参考了Airbnb的JavaScript风格规范。当然还有google...

21170
来自专栏java一日一条

最全面的 Android 编码规范指南

这份文档参考了 Google Java 编程风格规范和 Google 官方 Android 编码风格规范。该文档仅供参考,只要形成一个统一的风格,见量知其意就可...

17040
来自专栏大数据平台TBDS

Hive 时间转换函数使用心得

Hive sql 与传统的 oracle 或者mysql 的时间转换函数有一些不同,对于想将传统数据库迁移到hdfs 用 hive sql 进行处理的任务,如何...

4.8K120
来自专栏灯塔大数据

干货 | 数据科学入门必读:如何使用正则表达式?

有时候,这些数据中会包含大量文本语料。比如,假如我们需要搞清楚「xxx文件 」中谁给谁发送过邮件,那么我们就要筛查 1150 万份文档!我们可以采用人工方式,亲...

13520
来自专栏欧阳大哥的轮子

深入解构iOS的block闭包实现原理

在iOS4出来后,苹果公司在OC中推出了block机制(也许更早就有了)。并且在后续的版本中大量的推广和使用了这项技术,比如对视图动画API的改版,比如GCD技...

9830
来自专栏恰童鞋骚年

【译】.NET中六个重要的概念:栈、堆、值类型、引用类型、装箱和拆箱

  一来是为了感受国外优秀技术社区知名博主的高质量文章,二来是为了复习对.NET技术的基础拾遗达到温故知新的效果,最后也是为了锻炼一下自己的英文读写能力。因为是...

7920
来自专栏JAVA高级架构

java面试需要掌握知识点

重点知识 由于我面试的JAVA开发工程师,针对于JAVA,需要理解的重点内容有: JVM内存管理机制和垃圾回收机制(基本每次面试都会问,一定要搞得透彻) JVM...

38250
来自专栏JavaEdge

设计模式实战-迭代器模式

迭代器是为容器服务的,那什么是容器呢? 能容纳对象的所有类型都可以称之为容器,例如Collection集合类型、Set类型等,迭代器模式就是为解决遍历这些容器中...

31720
来自专栏余林丰

Effective Java通俗理解(下)

第31条:用实例域代替序数   枚举类型有一个ordinal方法,它范围该常量的序数从0开始,不建议使用这个方法,因为这不能很好地对枚举进行维护,正确应该是利用...

27790

扫码关注云+社区

领取腾讯云代金券