题意 : 中文题不详述。
思路 : 二维背包,dp[i][h]表示当前忍耐值为i的情况下,杀了h个怪得到的最大经验值,状态转移方程:
dp[i][h] = max(dp[i][h],dp[i-a[j].toler][h-1]+a[j].exper) ;
//
#include <stdio.h>
#include <string.h>
#include <iostream> using namespace std ; struct node
{
int exper ;
int toler ;
}a[] ; int dp[][] ; int main()
{
int n,m,k,s ;
while(~scanf("%d %d %d %d",&n,&m,&k,&s))
{
for(int i = ; i <= k ; i++)
scanf("%d %d",&a[i].exper,&a[i].toler) ;
memset(dp,,sizeof(dp)) ;
int ans = - ;
for(int i = ; i <= m ; i++)//当前忍耐度下得到的最多经验
{
for(int j = ; j <= k ; j++)
{
for(int h = ; h <= s ; h++)
if(i >= a[j].toler)
dp[i][h] = max(dp[i][h],dp[i-a[j].toler][h-]+a[j].exper) ;
}
if(dp[i][s] >= n)
{
ans = m-i ;
break;
}
}
printf("%d\n",ans) ;
}
return ;
}
HDU 2159 FATE (DP 二维费用背包)的更多相关文章
-
HDU 2159 FATE(二维费用背包)
FATE Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submi ...
-
HDU 2159 FATE(二维全然背包)
中文题目就不用解释了 就是裸的二维全然背包 d[i][j]表示消耗i忍耐杀j个怪最多可获得的经验 然后就用全然背包来做了 二维背包背包只是是多了一重循环 <span style=&quo ...
-
HDU 2159 FATE (二维完全背包
FATE http://acm.hdu.edu.cn/showproblem.php?pid=2159 Problem Description 最近xhd正在玩一款叫做FATE的游戏,为了得到*装备 ...
-
HDU 2159 FATE【二维完全背包】
题意:xhd玩游戏,还需要n个经验值升级,还留有m的忍耐度,但是他最多打s只怪,给出k个怪的经验值a[i],以及消耗的忍耐度b[i],问xhd能不能升级-- 因为有两个限定,忍耐度,和最多打s只怪(即 ...
-
hdu 2159 FATE (二维完全背包)
链接:http://acm.hdu.edu.cn/showproblem.php?pid=2159 思路: dp[j][k] 代表消耗耐久度j,干掉k个敌人获得的经验值. 状态转移方程为: dp[j] ...
-
HDU - 2159 FATE(二维dp之01背包问题)
题目: 思路: 二维dp,完全背包,状态转移方程dp[i][z] = max(dp[i][z], dp[i-1][z-a[j]]+b[j]),dp[i][z]表示在杀i个怪,消耗z个容忍度的情况下 ...
-
C. Arcade dp二维费用背包 + 滚动数组 玄学
http://codeforces.com/gym/101257/problem/C 询问从左上角走到右下角,每次只能向右或者向左,捡起三种物品算作一个logo,求最多能得到多少个logo. 设dp[ ...
-
HDOJ(HDU).2159 FATE (DP 带个数限制的完全背包)
HDOJ(HDU).2159 FATE (DP 带个数限制的完全背包) 题意分析 与普通的完全背包大同小异,区别就在于多了一个个数限制,那么在普通的完全背包的基础上,增加一维,表示个数.同时for循环 ...
-
Regionals 2014 >;>; Asia - Taichung 7003 - A Balance Game on Trees 树形DP + 二维费用背包
https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_probl ...
随机推荐
-
Django数据操作F和Q、model多对多操作、Django中间件、信号、读数据库里的数据实现分页
models.tb.objects.all().using('default'),根据using来指定在哪个库里查询,default是settings中配置的数据库的连接名称. 外话:django中引 ...
-
DOCKER windows安装
DOCKER windows安装 1.下载程序包 2. 设置环境变量 3. 启动DOCKERT 4. 分析start.sh 5. 利用SSH工具管理 6. 下载镜像 6.1 下载地址 6.2 用FTP ...
-
Hangover 分类: POJ 2015-06-11 10:34 12人阅读 评论(0) 收藏
Hangover Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 108765 Accepted: 53009 Descr ...
-
软件开发过程文档-cgaowei
鸡肋——食之无味,弃之可惜”,软件开发过程文档遭遇了鸡肋一样的境遇. 目前敏捷软件开发过程非常流行.相对于软件开发过程文档,敏捷软件开发过程更加重视可运行的程序.关于软件开发过程文档,两个极端都是不可 ...
-
window.showModalDialog刷新父窗口和本窗口的方法及注意
window.showModalDialog刷新父窗口和本窗口的方法及注意: 一.刷新父窗口的方法: A.使用window.returnValue给父窗口传值,然后根据值判断是否刷新. 在w ...
-
C++中的类继承(1) 三种继承方式
继承是使代码可以复用的重要手段,也是面向对象程序设计的核心思想之一.简单的说,继承是指一个对象直接使用另一对象的属性和方法.继承呈现了 面向对象程序设 计的层次结构, 体现了 由简单到复杂的认知过程. ...
-
Words used when reading Redis documents
Redis-----------------First pageevolution n.演变,进化,发展 closely adv.紧密地trade off 交换物品,权衡achieved adj.高度 ...
-
第15章-输入/输出 --- 理解Java的IO流
(一)理解Java的IO流 JAVA的IO流是实现输入/输出的基础,它可以方便地实现数据的输入/输出操作,在Java中把不同的输入/输出(键盘.文件.网络连接等)抽象表述为"流"( ...
-
解决HUE报错MultipleObjectsReturned: get() returned more than one Document2 -- it returned 2!
表现:界面上报错:,刚登陆进去就能看到,点击执行也会出现.日志里报: Traceback (most recent call last): File "/home/work/hue-3.10 ...
-
递归方式 DOM 解析(parse) XML
friends.xml <span style="font-size:16px;"><?xml version="1.0" encoding= ...