POJ-1661-Help Jimmy(DP, 递推)
链接:
https://vjudge.net/problem/POJ-1661
题意:
"Help Jimmy" 是在下图所示的场景上完成的游戏。
场景中包括多个长度和高度各不相同的平台。地面是最低的平台,高度为零,长度无限。
Jimmy老鼠在时刻0从高于所有平台的某处开始下落,它的下落速度始终为1米/秒。当Jimmy落到某个平台上时,游戏者选择让它向左还是向右跑,它跑动的速度也是1米/秒。当Jimmy跑到平台的边缘时,开始继续下落。Jimmy每次下落的高度不能超过MAX米,不然就会摔死,游戏也会结束。
设计一个程序,计算Jimmy到底地面时可能的最早时间。
思路:
刚开始考虑记忆化搜索,Dp[i][j], 记录到i平台, j位置落地的最小值, 然后超内存了.
因为每个位置只有左和右,所有考虑走左和走右, 从前一项推出当前项.
代码:
include
include
include
include
//#include <memory.h>
include
include
include
include
include <math.h>
include
include
include <assert.h>
include
include
include
define MINF 0x3f3f3f3f
using namespace std;
typedef long long LL;
const LL MOD = 20090717;
const int MAXN = 1e3+10;
struct Node
{
int l, r;
int h;
bool operator < (const Node& that) const
{
return this->h > that.h;
}
}node[MAXN];
int n, x, y, m;
int Dp[MAXN][2];
void CalLeft(int i)
{
int k = i+1;
while (k <= n && node[i].h - node[k].h <= m)
{
if (node[i].l >= node[k].l && node[i].l <= node[k].r)
{
Dp[i][0] = node[i].h-node[k].h+min(Dp[k][0]+abs(node[i].l-node[k].l), Dp[k][1]+abs(node[i].l-node[k].r));
return;
}
k++;
}
if (node[i].h - node[k].h > m)
Dp[i][0] = MINF;
else
Dp[i][0] = node[i].h;
return;
}
void CalRight(int i)
{
int k = i+1;
while (k <= n && node[i].h-node[k].h <= m)
{
if (node[i].r >= node[k].l && node[i].r <= node[k].r)
{
Dp[i][1] = node[i].h-node[k].h+min(Dp[k][0]+abs(node[i].r-node[k].l), Dp[k][1]+abs(node[i].r-node[k].r));
return;
}
k++;
}
if (node[i].h - node[k].h > m)
Dp[i][1] = MINF;
else
Dp[i][1] = node[i].h;
return;
}
int main()
{
int t;
scanf("%d", &t);
while (t--)
{
memset(Dp, 0, sizeof(Dp));
scanf("%d%d%d%d", &n, &x, &y, &m);
for (int i = 1;i <= n;i++)
scanf("%d%d%d", &node[i].l, &node[i].r, &node[i].h);
sort(node+1, node+1+n);
node[0].l = node[0].r = x;
node[0].h = y;
node[n+1].l = -20000, node[n+1].r = 20000;
node[n+1].h = 0;
for (int i = n;i >= 0;i--)
{
CalLeft(i);
CalRight(i);
}
printf("%d\n", min(Dp[0][0], Dp[0][1]));
}
return 0;
}```c++
最新文章
- LVS+Keepalived搭建MyCAT高可用负载均衡集群
- Lucas定理
- 在Ubuntu上为Android系统编写Linux内核驱动程序(老罗学习笔记1)
- sqlMetal用法和例子 自定义DBML
- css学习笔记二
- 小代码编写神器:LINQPad 使用入门
- inux中shell变量$#,$@,$0,$1,$2的含义
- 201521123064 《Java程序设计》第4周学习总结
- Python案例分享
- Python中的算数运算符
- JAVA的基本数据类型和类型转换
- xorm中的几个坑
- Windows10环境下使用VisualSVN server搭建SVN服务器
- 12C -- ORA-65005: missing or invalid file name pattern for file
- 四川省赛 SCU - 4438
- pstack 故障排除思路
- 微信小程序 - 自定义switch切换(示例)
- Logstash使用jdbc同步MySQL中的数据
- Apche Kafka 的生与死 – failover 机制详解
- jdbcType 与 Java type