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

推荐阅读

int
九度OnlineJudge之1002：Grading问题的解决方法

本文介绍了九度OnlineJudge中的1002题目“Grading”的解决方法。该题目要求设计一个公平的评分过程，将每个考题分配给3个独立的专家，如果他们的评分不一致，则需要请一位裁判做出最终决定。文章详细描述了评分规则，并给出了解决该问题的程序。 ... [详细]

蜡笔小新 2023-12-14 13:00:09
int
Open judge C16H: Magical Balls 快速幂+逆元问题解析

本文主要解析了Open judge C16H问题中涉及到的Magical Balls的快速幂和逆元算法，并给出了问题的解析和解决方法。详细介绍了问题的背景和规则，并给出了相应的算法解析和实现步骤。通过本文的解析，读者可以更好地理解和解决Open judge C16H问题中的Magical Balls部分。 ... [详细]

蜡笔小新 2023-12-14 12:03:27
int
差分约束系统求解House Man跳跃问题的思路与方法

本文讨论了使用差分约束系统求解House Man跳跃问题的思路与方法。给定一组不同高度，要求从最低点跳跃到最高点，每次跳跃的距离不超过D，并且不能改变给定的顺序。通过建立差分约束系统，将问题转化为图的建立和查询距离的问题。文章详细介绍了建立约束条件的方法，并使用SPFA算法判环并输出结果。同时还讨论了建边方向和跳跃顺序的关系。 ... [详细]

蜡笔小新 2023-12-14 11:49:51
int
UVALive6575 Odd and Even Zeroes 数位dp+找规律

本文介绍了UVALive6575题目Odd and Even Zeroes的解法，使用了数位dp和找规律的方法。阶乘的定义和性质被介绍，并给出了一些例子。其中，部分阶乘的尾零个数为奇数，部分为偶数。 ... [详细]

蜡笔小新 2023-12-13 14:19:28
int
[CF949D]Curfew 二分答案是个不错的开头，困难部分在于如何检查

本文介绍了一个题目的解法，通过二分答案来解决问题，但困难在于如何进行检查。文章提供了一种逃逸方式，通过移动最慢的宿管来锁门时跑到更居中的位置，从而使所有合格的寝室都居中。文章还提到可以分开判断两边的情况，并使用前缀和的方式来求出在任意时刻能够到达宿管即将锁门的寝室的人数。最后，文章提到可以改成O(n)的直接枚举来解决问题。 ... [详细]

蜡笔小新 2023-12-13 09:08:55
int
P1651 塔 (动态规划) 的最大高度计算方法

本文介绍了P1651题目的描述和要求，以及计算能搭建的塔的最大高度的方法。通过动态规划和状压技术，将问题转化为求解差值的问题，并定义了相应的状态。最终得出了计算最大高度的解法。 ... [详细]

蜡笔小新 2023-12-13 19:52:19
int
使用多进程实现TCP服务端的优势和注意事项

本文介绍了为什么要使用多进程处理TCP服务端，多进程的好处包括可靠性高和处理大量数据时速度快。然而，多进程不能共享进程空间，因此有一些变量不能共享。文章还提供了使用多进程实现TCP服务端的代码，并对代码进行了详细注释。 ... [详细]

蜡笔小新 2023-12-13 18:25:30
int
二叉树层序创建问题的解决方法

本文介绍了解决二叉树层序创建问题的方法。通过使用队列结构体和二叉树结构体，实现了入队和出队操作，并提供了判断队列是否为空的函数。详细介绍了解决该问题的步骤和流程。 ... [详细]

蜡笔小新 2023-12-13 18:20:50
int
CF：3D City Model（小思维）问题解析和代码实现

本文通过解析CF：3D City Model问题，介绍了问题的背景和要求，并给出了相应的代码实现。该问题涉及到在一个矩形的网格上建造城市的情景，每个网格单元可以作为建筑的基础，建筑由多个立方体叠加而成。文章详细讲解了问题的解决思路，并给出了相应的代码实现供读者参考。 ... [详细]

蜡笔小新 2023-12-13 14:17:11
int
3.223.28周学习总结中的贪心作业收获及困惑

本文是对3.223.28周学习总结中的贪心作业进行总结，作者在解题过程中参考了他人的代码，但前提是要先理解题目并有解题思路。作者分享了自己在贪心作业中的收获，同时提到了一道让他困惑的题目，即input details部分引发的疑惑。 ... [详细]

蜡笔小新 2023-12-13 03:42:02
int
clone的fork与pthread_create创建线程有何不同

本文讨论了clone的fork与pthread_create创建线程的不同之处。进程是一个指令执行流及其执行环境，其执行环境是一个系统资源的集合。在调用系统调用fork创建一个进程时，子进程只是完全复制父进程的资源，这样得到的子进程独立于父进程，具有良好的并发性。但是二者之间的通讯需要通过专门的通讯机制，另外通过fork创建子进程系统开销很大。因此，在某些情况下，使用clone或pthread_create创建线程可能更加高效。 ... [详细]

蜡笔小新 2023-12-12 20:00:06
int
HDU 2372 El Dorado（DP）的最长上升子序列长度求解方法

本文介绍了解决HDU 2372 El Dorado问题的一种动态规划方法，通过循环k的方式求解最长上升子序列的长度。具体实现过程包括初始化dp数组、读取数列、计算最长上升子序列长度等步骤。 ... [详细]

蜡笔小新 2023-12-14 15:08:18
int
C# 7.0 新特性：基于Tuple的“多”返回值方法

本文介绍了C# 7.0中基于Tuple的“多”返回值方法的使用。通过对C# 6.0及更早版本的做法进行回顾，提出了问题：如何使一个方法可返回多个返回值。然后详细介绍了C# 7.0中使用Tuple的写法，并给出了示例代码。最后，总结了该新特性的优点。 ... [详细]

蜡笔小新 2023-12-13 19:55:20
int
Linux环境变量函数getenv、putenv、setenv和unsetenv详解

本文详细解释了Linux中的环境变量函数getenv、putenv、setenv和unsetenv的用法和功能。通过使用这些函数，可以获取、设置和删除环境变量的值。同时给出了相应的函数原型、参数说明和返回值。通过示例代码演示了如何使用getenv函数获取环境变量的值，并打印出来。 ... [详细]

蜡笔小新 2023-12-13 12:01:03
java
Java学习笔记之面向对象编程（OOP）

本文介绍了Java学习笔记中的面向对象编程（OOP）内容，包括OOP的三大特性（封装、继承、多态）和五大原则（单一职责原则、开放封闭原则、里式替换原则、依赖倒置原则）。通过学习OOP，可以提高代码复用性、拓展性和安全性。 ... [详细]

蜡笔小新 2023-12-13 08:44:30

森tu罗宝殿

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

Tags | 热门标签

RankList | 热门文章