ZOJ 2972-Hurdles of 110m(背包dp)_梧桐下的四叶草-程序员宝宝

技术标签: zoj  动态规划  dp  

H - Hurdles of 110m
Time Limit:2000MS     Memory Limit:65536KB     64bit IO Format:%lld & %llu

Description

In the year 2008, the 29th Olympic Games will be held in Beijing. This will signify the prosperity of China and Beijing Olympics is to be a festival for people all over the world as well.

Liu Xiang is one of the famous Olympic athletes in China. In 2002 Liu broke Renaldo Nehemiah's 24-year-old world junior record for the 110m hurdles. At the 2004 Athens Olympics Games, he won the gold medal in the end. Although he was not considered as a favorite for the gold, in the final, Liu's technique was nearly perfect as he barely touched the sixth hurdle and cleared all of the others cleanly. He powered to a victory of almost three meters. In doing so, he tied the 11-year-old world record of 12.91 seconds. Liu was the first Chinese man to win an Olympic gold medal in track and field. Only 21 years old at the time of his victory, Liu vowed to defend his title when the Olympics come to Beijing in 2008.

In the 110m hurdle competition, the track was divided into N parts by the hurdle. In each part, the player has to run in the same speed; otherwise he may hit the hurdle. In fact, there are 3 modes to choose in each part for an athlete -- Fast Mode, Normal Mode and Slow Mode. Fast Mode costs the player T1 time to pass the part. However, he cannot always use this mode in all parts, because he needs to consume F1 force at the same time. If he doesn't have enough force, he cannot run in the part at the Fast Mode. Normal Mode costs the player T2 time for the part. And at this mode, the player's force will remain unchanged. Slow Mode costs the player T3 time to pass the part. Meanwhile, the player will earn F2 force as compensation. The maximal force of a player is M. If he already has M force, he cannot earn any more force. At the beginning of the competition, the player has the maximal force.

The input of this problem is detail data for Liu Xiang. Your task is to help him to choose proper mode in each part to finish the competition in the shortest time.

Input

Standard input will contain multiple test cases. The first line of the input is a single integer T (1 <= T <= 50) which is the number of test cases. And it will be followed by T consecutive test cases.

Each test case begins with two positive integers N and M. And following N lines denote the data for the N parts. Each line has five positive integers T1 T2 T3 F1 F2. All the integers in this problem are less than or equal to 110.

Output

Results should be directed to standard output. The output of each test case should be a single integer in one line, which is the shortest time that Liu Xiang can finish the competition.

Sample Input

2
1 10
1 2 3 10 10
4 10
1 2 3 10 10
1 10 10 10 10
1 1 2 10 10
1 10 10 10 10

Sample Output

1
6

Hint

For the second sample test case, Liu Xiang should run with the sequence of Normal Mode, Fast Mode, Slow Mode and Fast Mode.


参考资料:

      转自:蚂蚁大战大象

题意:刘翔跨栏问题,初始有M能量,有N块区域需要跑,在第i可以使用3种模式:

1.Fast模式 通过第i个区域需要用T1[i]的时间,需要消耗F1[i]能量.

2.Normal模式 通过第i个区域需要用T2[i]的时间,不需要消耗能量.

3.Slow模式 通过第i个屈戌需要T3[i]的时间,能增加F2[i]能量,但是增加后的能量不能超过总能量M.

求通过N个区域的最短时间.

还是比较简单的DP,阶段和决策很清楚,写起来很流畅.

设dp[i][j]为跑过前i个区域剩余能量为j时的最少用时.

那么dp[0][j]自然就是0,答案就是min{dp[N][j] | 0<= j <= M}

1.如果在第i区域用Fast模式,那么dp[i + 1][j - F1[i]] = min(dp[i + 1][j - F1[i]], dp[i][j] + T1[i]),注意这里的j - F1[i]不能小于0.

2.如果在第i区域用Normal模式,那么dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + T2[i]).

3.如果在第i区域用Slow模式,那么dp[i + 1][j + F2[i]] = min(dp[i + 1][j + F2[i]], dp[i][j] + T2[i]),注意这里的j + F2[i]如果超过了M,那么要变成M.


   这题不参考上面的资料都不知道那个dp的动态转移方程是如何弄出来的,看一下子就看懂了,但要自己亲自去写的话却无从下手。。。。或许是dp没训练过吧,所以脑袋抽了。


AC代码:


#include<iostream>
#include<sstream>
#include<algorithm>
#include<cstring>
#include<string>
#include<cstdio>
#include<stack>
using namespace std;
#define T 500
#define inf 0x3f3f3f3f
int main()
{
#ifdef zsc
	freopen("input.txt","r",stdin);
#endif
	int N,n,m,i,j;
	int dp[T][T];
	int T1[T],T2[T],T3[T],F1[T],F2[T];
	scanf("%d",&N);
	while(N--)
	{
		scanf("%d%d",&n,&m);
		for(i=0;i<n;++i){
			scanf("%d%d%d%d%d",&T1[i],&T2[i],&T3[i],&F1[i],&F2[i]);
		}
		memset(dp,inf,sizeof(dp));
		for(i=0;i<=m;++i){
			dp[0][i] = 0;
		}
		int ans = inf;
		for(i=0;i<n;++i){
			for(j=0;j<=m;++j){
				if(j>=F1[i]&&dp[i+1][j-F1[i]]>dp[i][j]+T1[i]){//第一种
				   dp[i+1][j-F1[i]] = dp[i][j]+T1[i];
				}
				if(dp[i+1][j]>dp[i][j]+T2[i]){//第二种
					dp[i+1][j] = dp[i][j] + T2[i];
				}
				int tmp = min(m,j+F2[i]);
				if(dp[i+1][tmp]>dp[i][j]+T3[i]){//第三种
					dp[i+1][tmp] = dp[i][j] + T3[i];
				}
			}
		}
		for(i=0;i<=m;++i){
			ans = min(ans,dp[n][i]);
		}
		printf("%d\n",ans);
	}
	return 0;
}


版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/zsc2014030403015/article/details/49721475

智能推荐

Android Studio 的 NDK 配置_ayang1986的专栏-程序员宝宝_as ndk 设置

文章目录 I . 源码编译配置 II . 构建脚本配置 III . NDK 函数库打包配置 IV . Java 与 C 代码示例 V . CMake 配置 ( CMakeLists.txt ) VI . ndkBuild 配置 ( Android.mk ) VII . 博客相关资源下载 I . 源码编译配置1 . 源码编译配置 :① 配置位置 :Module 级别的 build.gradle 中进行配置 ;...

基于IAR for RH850的瑞萨RH850 FCL库用法介绍_announced1的博客-程序员宝宝_瑞萨rh850

博主联系方式:QQ:1256153255 ,email:[email protected] for get 瑞萨RH850F1x开发板和瑞萨E1仿真器1、简介本文介绍了RH850 FCL的使用以及相关的经验技巧,使用的环境如下MCU:瑞萨RH850F1K型号:R7F701557编译器:IAR for RH850编译器版本:IAR Embeded Workbench for Renesas RH850 V2.10.1IAR Embeded Workbench shared

15、Mybatis 动态 sql 有什么用?执行原理?有哪些动态 sql?_IT匠人的博客-程序员宝宝_mybatis动态sql有什么用

Mybatis 动态 sql 可以在 Xml 映射文件内,以标签的形式编写动态 sql,执行原理 是根据表达式的值 完成逻辑判断并动态拼接 sql 的功能。 Mybatis 提供了 9 种动态 sql 标签:trim | where | set | foreach | if | choose | when | otherwise | bind...

IDEA找不到配置文件cannot resolve file spring-mvc.xml解决方法 日常犯错_acwing的博客-程序员宝宝

出现了 这样的问题对应的 &lt;param-value&gt;classpath*:&lt;/param-value&gt;以及&lt;param-value&gt;classpath:&lt;/param-value&gt;二者的区别第一个 所有对应的路径都会查找第二个 是 准确查找 只会在你标记的路径下 进行查找、上述 问题解决之后再进行 刷新 重启idea 就可以解决了...

spring-mvc 用注解实现spring-mvc的基本开发_abaidaye的博客-程序员宝宝

用注解实现spring-mvc的基本开发maven的配置&lt;dependency&gt; &lt;groupId&gt;org.springframework&lt;/groupId&gt; &lt;artifactId&gt;spring-webmvc&lt;/artifactId&gt; &lt;version&gt;5.2.0.RELEASE&lt;/version&gt;&lt;/dependency&gt;--------------------------

OpenWrt之DNS设置_NueXini的博客-程序员宝宝_openwrt设置dns

文章目录OpenWrt之DNS设置0.前言1.WAN口2.Lan口3.LAN口DHCP选项4.DHCP/DNS5.总结参考(Thanks)附录.DHCP OPTIONOpenWrt之DNS设置0.前言本文不涉及smartdns、adguardhome、dns防污染等内容,只介绍DNS的设置1.WAN口保存&amp;应用后 客户机发出dns解析请求后路由器用上面的dns回应2.Lan口进入openwrt的luci页面。在 网络&gt;网卡&gt;LAN 选择编辑保存&amp;应用后,路

随便推点

计算机网络_aaronlanni的博客-程序员宝宝_csdn计算机网络

一、计算机的发展 1、计算机网络的功能 a、连通性:使得上网用户之间可以交换信息 b、共享:共享资源 2、因特网的概述 网络:由若干结点和连接着这些结点的链路组成,网络中的结点可以是计算机、集线器、路由器、交换机等,(互联网是“网络中的网络”,将网络与网络通过路由器连接在一起) 因特网(Internet):世界上最大的网络,网络是将许多计算机连接在一起,而因特网是将许多网络连接在一起 ...

cookie规范(RFC6265)翻译_weixin_30508309的博客-程序员宝宝

来源:https://github.com/renaesop/blog/issues/4RFC 6265 要点翻译1.简介本文档定义了HTTP Cookie以及HTTP头的Set-Cookie字段。通过使用Set-Cookie头,一个HTTP服务器可以传递name/value键值对以及相对应的元数据(所谓的cookies)到user agent。当user agent向服务...

微信小程序使用七牛云对象存储保存图片和文件_美奇软件开发工作室-程序员宝宝_七牛云存储 微信小程序

先给大家看效果图,如下:一、开通七牛云对象存储服务(免费的)官网:https://www.qiniu.com/,实名认证后,创建一个空间,用于保存文件二、获取AccessKey和SecretKey密钥,在“个人中心”→ “密钥管理”中三、thinkphp后端:生成七牛云上传凭证Token1、下载七牛云php依赖库,下载地址:https://github.co...

卡西欧科学计算机使用方法,卡西欧计算器使用说明_袁先康的博客-程序员宝宝

日常办公中计算器是必不可少的一个工具。可是你知道你手中的这个工具的所有功能吗?下面就写一下卡西欧计算器使用说明,下面就以卡西欧DZ-12S为样品进行介绍:1.右上角的可以左右调节的F-4-2-1-0-ADD2叫做小数位选择器:F:显示不做任何取舍数值的浮点小数。(常用设置在这里不必调整)4-2-1-0:就是为CUT-UP-5/4功能指定小数位数。ADD2:自动为全部数值加上小数点后2位,相当于除以...

Pytorch中的卷积、空洞卷积和组卷积_a171232886的博客-程序员宝宝_pytorch中空洞卷积

Pytorch中的卷积、空洞卷积和组卷积标准卷积Conv2d具体操作空洞卷积组卷积参考文献标准卷积Conv2d最基础的卷积。下面图虽然丑了点,但足够说明问题了。注:(1) kernel的值在初始化中是随机生成的,可以每个值之间都不一样。 (2)每个通道只对应一个bias值。具体操作torch.nn.Conv2d(in_channels, out_channels, kernel_size, stride=1, padding=0, dilation=1, groups=1, bias=

成长路线 - Android移动开发架构师_KarenChia - 翟坤-程序员宝宝

基础知识进阶、常用高级UI、架构师必备技能、常用三方框架解读、源码解析…文章整理、总结Android架构师成长中的各类知识要点,持续更新。Java基础进阶Java开发中的泛型