Archives: 寒冰王座 HDU - 1248 贪心

Advertisement

HDU 1248 寒冰王座 完全背包 水题

这个题目 转化为背包的时候 可以看到 物品价值 背包容量 都有 但是没有物品的体积 我们要求的是骑士最大能花的钱数,由于缺少物品的体积 我们可以这样思考,骑士要的钞票面额 就是背包大小 骑士向背包里装物品 物品价值不能超过背包的体积 这时 物品的最大价值是多少.因此我们可以把物品的体积看成物品的价值 ,这时 背包恰好不能再放入物品的状态下 既是物品价值最大的情况 也就是骑士花的钱最多的情况.因为物品价值=物品体积 所以 dp[N]不会超过N 状态转移方程: 题目及AC代码如下 寒冰王座 Time

杭电 HDU 1248 寒冰王座

寒冰王座 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 12453 Accepted Submission(s): 6322 Problem Description 不死族的巫妖王发工资拉,死亡骑士拿到一张N元的钞票(记住,只有一张钞票),为了防止自己在战斗中频繁的死掉,他决定给自己买一些道具,于是他来到了地精商店前. 死亡骑士:"我要买道

[完全背包]HDOJ 1248寒冰王座

传送门:寒冰王座 寒冰王座 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 9341 Accepted Submission(s): 4715 Problem Description 不死族的巫妖王发工资拉,死亡骑士拿到一张N元的钞票(记住,只有一张钞票),为了防止自己在战斗中频繁的死掉,他决定给自己买一些道具,于是他来到了地精商店前. 死亡

寒冰王座(hd1248)

寒冰王座 Problem Description 不死族的巫妖王发工资拉,死亡骑士拿到一张N元的钞票(记住,只有一张钞票),为了防止自己在战斗中频繁的死掉,他决定给自己买一些道具,于是他来到了地精商店前. 死亡骑士:"我要买道具!" 地精商人:"我们这里有三种道具,血瓶150块一个,魔法药200块一个,无敌药水350块一个." 死亡骑士:"好的,给我一个血瓶." 说完他掏出那张N元的大钞递给地精商人. 地精商人:"我忘了提醒你了,我们这

寒冰王座

寒冰王座 Time Limit : 2000/1000ms (Java/Other) Memory Limit : 65536/32768K (Java/Other) Total Submission(s) : 15 Accepted Submission(s) : 10 Font: Times New Roman | Verdana | Georgia Font Size: ← → Problem Description 不死族的巫妖王发工资拉,死亡骑士拿到一张N元的钞票(记住,只有一张钞票)

杭电hdu 1248 寒冰王座 完全背包

http://acm.hdu.edu.cn/showproblem.php?pid=1248 注意与0-1背包的区别 #include <stdio.h> #include <string.h> int max(int a, int b) { return a > b ? a : b; } int main() { int t; int n; int arr[3] = {150, 200, 350}; int i, j; int dp[10002]; scanf("

HDU 1248(寒冰王座)基础完全背包

求小费最小,那就是求花费钱最多 完全背包 代码: #include<stdio.h> #include<string.h> int dp[10010]; int n; int Max(int a,int b) { return a>b?a:b; } int main() { int i,j; int a[10]; int T; scanf("%d",&T); while(T--) { a[0]=150,a[1]=200,a[2]=350; mems

hdu ——寒冰王座——完全背包问题

Problem Description 不死族的巫妖王发工资拉,死亡骑士拿到一张N元的钞票(记住,只有一张钞票),为了防止自己在战斗中频繁的死掉,他决定给自己买一些道具,于是他来到了地精商店前. 死亡骑士:"我要买道具!" 地精商人:"我们这里有三种道具,血瓶150块一个,魔法药200块一个,无敌药水350块一个." 死亡骑士:"好的,给我一个血瓶." 说完他掏出那张N元的大钞递给地精商人. 地精商人:"我忘了提醒你了,我们这里没有找客

hdu 1735(贪心) 统计字数

戳我穿越:http://acm.hdu.edu.cn/showproblem.php?pid=1735 对于贪心,二分,枚举等基础一定要掌握的很牢,要一步一个脚印走踏实 这是道贪心的题目,要有贪心的意识. 首先将所有为0的地方统计,因为是求最小的字数,所有最后一行后面的0可以看为空格直接减掉, 因为有m段(一定包括第一行),再减去m*2,最后枚举每行,将至少前两个为0的上一行的最后有多少 的0统计起来排序,再依次减去前m-1个大的,这样就保证了得到的答案是符合条件中最小的 code 1 #inc

HDU 2111 Saving HDU【贪心】

解题思路:排序后贪心,和fatmouse's trade 类似 Saving HDU Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 5837 Accepted Submission(s): 2692 Problem Description 话说上回讲到海东集团面临内外交困,公司的元老也只剩下XHD夫妇二人了.显然,作为多年拼搏的商人,XHD

HDU 2111 Saving HDU(贪心,01背包)

Problem Description 话说上回讲到海东集团面临内外交困,公司的元老也只剩下XHD夫妇二人了.显然,作为多年拼搏的商人,XHD不会坐以待毙的. 一天,当他正在苦思冥想解困良策的时候,突然想到了自己的传家宝,那是公司成立的时候,父亲作为贺礼送来的一个锦囊,徐父当时交代,不到万不得已的时候,不要打开它."现在不正是最需要的时候吗?",一边想,XHD一边找到了这个精心保管的锦囊,打开一看,里面只有一句话"杭城北麓千人洞有宝". 二话不说,XHD拿起一个大口

HDU 1248 背包问题之完全背包

http://acm.hdu.edu.cn/showproblem.php?pid=1248 Problem Description 不死族的巫妖王发工资拉,死亡骑士拿到一张N元的钞票(记住,只有一张钞票),为了防止自己在战斗中频繁的死掉,他决定给自己买一些道具,于是他来到了地精商店前. 死亡骑士:"我要买道具!" 地精商人:"我们这里有三种道具,血瓶150块一个,魔法药200块一个,无敌药水350块一个." 死亡骑士:"好的,给我一个血瓶."

hdu 5720(贪心)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5720 官方题解: 考虑三角形三条边a,b,c  (a≥b) 的关系a−b<c,a+b>c ,即c∈(a−b,a+b) .令加入的边为c ,枚举所有边作为a 的情况.对于所有可行的b ,显然与a 相差最小的可以让(a−b,a+b) 覆盖范围最大,所以可以贪心地选择不大于a 的最大的b .于是我们可以先将边按长度排序,然后a i  和a i+1  建一条线段.线段并是不合法的部分.将所有线段按左端点排

hdu 4864 贪心

题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=4864 这是一道数据参数比较多的贪心,看了之后是不会做的..想了几天还是不会,刚开始直接想着用能完成的任务数目来写,结果忽视了钱数就无限wa. 无奈之下看了题解.这道题是这样子的,get (500*xi+2*yi) dollars.这是题目的原话,而yi的范围在100所以我们首先要考虑的是工作的时间其次才是难度.我们就可以这样进行排序了,第一层工作时间从长到短,第二层如果工作时间相同的话,以难度从大到

HDU 2831 (贪心)

题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=2831 题目大意:植物大战僵尸.给定种植植物时间间隔t,以及每个僵尸的到达时间v,生命d.问是否能赢. 解题思路: 按照打完每只Zombie之后剩余时间v-d,从小到大排序. 理由如下: 设打完第i只Zombie的剩余时间为:$Remain(v,d)=V-i*t-D$ 那么本题的目标函数为:$arg\max \limits_{i}\sum Remain(v,d)=V-i*t-D$ 所以,应当尽可能把

hdu 2037 贪心基础

hdu2037今年暑假不AC 题目大意:n个节目,开始时间以及结束时间已知,求最多可以完整看完的节目的个数. 思路:首先将节目按结束时间早晚排序,可以证明从第[1-n]个节目中选,最早结束的节目最后肯定在观看计划之内,从第[2-n]个节目中选,如果第二个节目不和前一个节目冲突那么肯定也在观看计划内,一次类推,遍历一次节目单.典型的贪心思想. code: #include <iostream> #include<cstdio> #include<algorithm> #d

hdu 1065(贪心)

Wooden Sticks Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 20938 Accepted: 8872 Description There is a pile of n wooden sticks. The length and weight of each stick are known in advance. The sticks are to be processed by a woodworking ma

hdu 1233(贪心算法,克鲁斯卡尔算法,并查集)

还是畅通工程 Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 25916 Accepted Submission(s): 11542 Problem Description 某省调查乡村交通状况,得到的统计表中列出了任意两村庄间的距离.省政府"畅通工程"的目标是使全省任何两个村庄间都可以实现公路交通(但不一定有直接的公路相连,只要能

HDU 1203 贪心或者DP

贪心策略是申请offer需要的钱越少越好,而成功率越高越好,所以按照需要的钱和成功率的比值从小到大排序,依次选择. #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #define MAXN 10010 using namespace std; struct node { int money; double p,r; bool operator<(const n