开发笔记: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;
}

推荐阅读

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

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

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

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

蜡笔小新 2024-12-27 18:14:31
char
Weight the Tree（树形dp）

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

蜡笔小新 2024-12-26 15:55:56
char
C语言链表动态创建：头插法与尾插法详解

本文详细介绍了C语言中链表的两种动态创建方法——头插法和尾插法，包括具体的实现代码和运行示例。通过这些内容，读者可以更好地理解和掌握链表的基本操作。 ... [详细]

蜡笔小新 2024-12-26 13:59:07
default
golang常用库：配置文件解析库/管理工具viper使用

golang常用库：配置文件解析库管理工具-viper使用-一、viper简介viper配置管理解析库，是由大神SteveFrancia开发，他在google领导着golang的 ... [详细]

蜡笔小新 2024-12-28 13:47:52
char
深入理解KMP算法中的next数组：北大OJ 2406题解

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

蜡笔小新 2024-12-28 11:30:01
default
编写有趣的VBScript恶作剧脚本

本文将介绍如何编写一些有趣的VBScript脚本，这些脚本可以在朋友之间进行无害的恶作剧。通过简单的代码示例，帮助您了解VBScript的基本语法和功能。 ... [详细]

蜡笔小新 2024-12-28 09:46:23
string
古代密码变换问题

本题探讨了一种字符串变换方法，旨在判断两个给定的字符串是否可以通过特定的字母替换和位置交换操作相互转换。核心在于找到这些变换中的不变量，从而确定转换的可能性。 ... [详细]

蜡笔小新 2024-12-28 09:18:22
default
使用Objective-C和dispatch库实现并发素数计算

本文介绍如何使用Objective-C结合dispatch库进行并发编程，以提高素数计数任务的效率。通过对比纯C代码与引入并发机制后的代码，展示dispatch库的强大功能。 ... [详细]

蜡笔小新 2024-12-28 08:44:35
default
C++: 实现基于类的四面体体积计算

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

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

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

蜡笔小新 2024-12-27 11:26:39
get
移动 UI 设计基础：打造简洁高效的用户界面

本章将深入探讨移动 UI 设计的核心原则，帮助开发者构建简洁、高效且用户友好的界面。通过学习设计规则和用户体验优化技巧，您将能够创建出既美观又实用的移动应用。 ... [详细]

蜡笔小新 2024-12-27 08:43:40
char
长春大学软件工程：二叉排序树实验报告

本实验主要探讨了二叉排序树（BST）的基本操作，包括创建、查找和删除节点。通过具体实例和代码实现，详细介绍了如何使用递归和非递归方法进行关键字查找，并展示了删除特定节点后的树结构变化。 ... [详细]

蜡笔小新 2024-12-26 15:32:56
shell
深入理解Python的os和sys模块

本文详细解析了Python中的os和sys模块，介绍了它们的功能、常用方法及其在实际编程中的应用。 ... [详细]

蜡笔小新 2024-12-26 22:04:19
string
Python学习笔记：使用pydoc工具查询文档

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

蜡笔小新 2024-12-26 17:05:56

森tu罗宝殿

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

Tags | 热门标签

RankList | 热门文章