开发笔记:poj1661

作者：森tu罗宝殿 | 来源：互联网 | 2023-10-13 09:21

HelpJimmy

Help Jimmy

Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions:13756		Accepted: 4566

Description

"Help Jimmy" 是在下图所示的场景上完成的游戏。
技术分享图片

场景中包括多个长度和高度各不相同的平台。地面是最低的平台，高度为零，长度无限。
Jimmy老鼠在时刻0从高于所有平台的某处开始下落，它的下落速度始终为1米/秒。当Jimmy落到某个平台上时，游戏者选择让它向左还是向右跑，它跑动的速度也是1米/秒。当Jimmy跑到平台的边缘时，开始继续下落。Jimmy每次下落的高度不能超过MAX米，不然就会摔死，游戏也会结束。
设计一个程序，计算Jimmy到底地面时可能的最早时间。

Input

第一行是测试数据的组数t（0 <= t <= 20）。每组测试数据的第一行是四个整数N，X，Y，MAX，用空格分隔。N是平台的数目（不包括地面），X和Y是Jimmy开始下落的位置的横竖坐标，MAX是一次下落的最大高度。接下来的N行每行描述一个平台，包括三个整数，X1[i]，X2[i]和H[i]。H[i]表示平台的高度，X1[i]和X2[i]表示平台左右端点的横坐标。1 <= N <= 1000，-20000 <= X, X1[i], X2[i] <= 20000，0 Jimmy的大小和平台的厚度均忽略不计。如果Jimmy恰好落在某个平台的边缘，被视为落在平台上。所有的平台均不重叠或相连。测试数据保证问题一定有解。

Output

对输入的每组测试数据，输出一个整数，Jimmy到底地面时可能的最早时间。

Sample Input

1
3 8 17 20
0 10 8
0 10 13
4 14 3

Sample Output

Source

POJ Monthly--2004.05.15 CEOI 2000

AC代码

#include
#include
#include<iostream>
#include
#include
#include<string>
#include
#include
#define DEBUG(x) cout <<#x <<" = " <using namespace std;
const int MAXN=1e3+10;
const int INF=1<<30;
int N,X,Y,MAX;
struct Plat{
int x1,x2,h;
bool operator<(const struct Plat &p)const
{
return h>p.h;
}
};
Plat plats[MAXN];
int LeftMinTime[MAXN];
int RightMinTime[MAXN];
int main()
{
// freopen("in.txt","r",stdin);
int t;
scanf("%d",&t);
while(t--){
scanf("%d %d %d %d",&N,&X,&Y,&MAX);
for(int i=0;i){
scanf("%d %d %d",&plats[i].x1
,&plats[i].x2,&plats[i].h);
}
plats[N].x1=X,
plats[N].x2=X,
plats[N++].h=Y;
sort(plats,plats+N);
LeftMinTime[N-1]=plats[N-1].h,
RightMinTime[N-1]=plats[N-1].h;
for(int i=N-2;i>=0;i--){
bool f=false;
int j;
///LeftMinTime
for(j=i+1;j){
bool l=plats[i].x1>=plats[j].x1&&plats[i].x1<=plats[j].x2;
if(l){
f=l;
break;
}
}
if(f){
int d=plats[i].h-plats[j].h;
if(d<=MAX){
int l=abs(plats[i].x1-plats[j].x1)+LeftMinTime[j]+plats[i].h-plats[j].h;
int r=abs(plats[i].x1-plats[j].x2)+RightMinTime[j]+plats[i].h-plats[j].h;
LeftMinTime[i]=min(l,r);
}
else
LeftMinTime[i]=INF;
}
else {
if(plats[i].h>MAX){
LeftMinTime[i]=INF;
}
else {
LeftMinTime[i]=plats[i].h;
}
}
///RightMinTime
f=false;
for(j=i+1;j){
bool r=plats[i].x2>=plats[j].x1&&plats[i].x2<=plats[j].x2;
if(r){
f=r;
break;
}
}
if(f){
int d=plats[i].h-plats[j].h;
if(d<=MAX){
int l=abs(plats[i].x2-plats[j].x1)+LeftMinTime[j]+plats[i].h-plats[j].h;
int r=abs(plats[i].x2-plats[j].x2)+RightMinTime[j]+plats[i].h-plats[j].h;
RightMinTime[i]=min(l,r);
}
else{
RightMinTime[i]=INF;
}
}
else {
if(plats[i].h>MAX){
RightMinTime[i]=INF;
}
else{
RightMinTime[i]=plats[i].h;
}
}
}
printf("%d
",LeftMinTime[0]);
}
return 0;
}

推荐阅读

post
扫描线三巨头 hdu1928hdu 1255 hdu 1542 [POJ 1151]

学习链接：http:blog.csdn.netlwt36articledetails48908031学习扫描线主要学习的是一种扫描的思想，后期可以求解很 ... [详细]

蜡笔小新 2024-12-26 20:04:36
post
USACO 2014 Jan - Moolympics区间记录优化算法

题目描述：给定n个半开区间[a, b)，要求使用两个互不重叠的记录器，求最多可以记录多少个区间。解决方案采用贪心算法，通过排序和遍历实现最优解。 ... [详细]

蜡笔小新 2024-12-27 18:14:31
post
Python学习笔记：使用pydoc工具查询文档

本文介绍了在Windows环境下使用pydoc工具的方法，并详细解释了如何通过命令行和浏览器查看Python内置函数的文档。此外，还提供了关于raw_input和open函数的具体用法和功能说明。 ... [详细]

蜡笔小新 2024-12-26 17:05:56
post
Weight the Tree（树形dp）

题目Link题目学习link1题目学习link2题目学习link3%%%受益匪浅！－－－－－&# ... [详细]

蜡笔小新 2024-12-26 15:55:56
post
深入理解KMP算法中的next数组：北大OJ 2406题解

本文详细探讨了KMP算法中next数组的构建及其应用，重点分析了未改良和改良后的next数组在字符串匹配中的作用。通过具体实例和代码实现，帮助读者更好地理解KMP算法的核心原理。 ... [详细]

蜡笔小新 2024-12-28 11:30:01
list
深入理解org.neo4j.helpers.collection.Iterators.single()方法及其应用

本文详细介绍了Java中org.neo4j.helpers.collection.Iterators.single()方法的功能、使用场景及代码示例，帮助开发者更好地理解和应用该方法。 ... [详细]

蜡笔小新 2024-12-28 10:51:55
foreach
深入解析 MVC 源码：ParameterDescriptor 与 Action 方法参数绑定

在前两篇文章中，我们探讨了 ControllerDescriptor 和 ActionDescriptor 这两个描述对象，分别对应控制器和操作方法。本文将基于 MVC3 源码进一步分析 ParameterDescriptor，即用于描述 Action 方法参数的对象，并详细介绍其工作原理。 ... [详细]

蜡笔小新 2024-12-27 15:26:10
eval
分页插件3指定到某一页

前言--页数多了以后需要指定到某一页（只做了功能，样式没有细调）html ... [详细]

蜡笔小新 2024-12-27 15:19:01
eval
C++: 实现基于类的四面体体积计算

本文介绍如何使用C++编程语言，通过定义类和方法来计算由四个三维坐标点构成的四面体体积。文中详细解释了四面体体积的数学公式，并提供了两种不同的实现方式。 ... [详细]

蜡笔小新 2024-12-27 14:31:39
list
UNP 第9章：主机名与地址转换

本章探讨了用于在主机名和数值地址之间进行转换的函数，如gethostbyname和gethostbyaddr。此外，还介绍了getservbyname和getservbyport函数，用于在服务器名和端口号之间进行转换。 ... [详细]

蜡笔小新 2024-12-27 11:26:39
range
寻找满足特定条件的整数N的最大和(a+b)

本文探讨了如何在给定整数N的情况下，找到两个不同的整数a和b，使得它们的和最大，并且满足特定的数学条件。 ... [详细]

蜡笔小新 2024-12-26 19:26:18
range
HDFS与Hive中的数据存储和管理机制

本文探讨了Hive中内部表和外部表的区别及其在HDFS上的路径映射，详细解释了两者的创建、加载及删除操作，并提供了查看表详细信息的方法。通过对比这两种表类型，帮助读者理解如何更好地管理和保护数据。 ... [详细]

蜡笔小新 2024-12-27 20:21:48
stream
Java 序列化接口详解

本文深入探讨了 Java 中的 Serializable 接口，解释了其实现机制、用途及注意事项，帮助开发者更好地理解和使用序列化功能。 ... [详细]

蜡笔小新 2024-12-27 15:06:12
utf-8
XNA 3.0 游戏编程：从 XML 文件加载数据

本文介绍如何在 XNA 3.0 游戏项目中从 XML 文件加载数据。我们将探讨如何将 XML 数据序列化为二进制文件，并通过内容管道加载到游戏中。此外，还会涉及自定义类型读取器和写入器的实现。 ... [详细]

蜡笔小新 2024-12-27 11:39:44
utf-8
C++构造函数与初始化列表详解

本文深入探讨了C++中构造函数的初始化列表，包括赋值与初始化的区别、初始化列表的使用规则、静态成员初始化等内容。通过实例和调试证明，详细解释了初始化列表在对象创建时的重要性。 ... [详细]

蜡笔小新 2024-12-26 14:19:13

森tu罗宝殿

这个家伙很懒，什么也没留下！

Tags | 热门标签

RankList | 热门文章