1.链接地址：
bailian.openjudge.cn/practice/1661
http://poj.org/problem?id=1661
2.题目：
- 总Time Limit:
- 1000ms
- Memory Limit:
- 65536kB
- 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 < H[i] < Y <= 20000（i = 1..N）。所有坐标的单位都是米。Jimmy的大小和平台的厚度均忽略不计。如果Jimmy恰好落在某个平台的边缘，被视为落在平台上。所有的平台均不重叠或相连。测试数据保证问题一定有解。
- Output
- 对输入的每组测试数据，输出一个整数，Jimmy到底地面时可能的最早时间。
- Sample Input
3 8 17 20
0 10 8
0 10 13
4 14 3- Sample Output
- Source
- POJ Monthly--2004.05.15 CEOI 2000
3.思路：
动态规划题目
注意Jimmy老鼠直接落到0高度的情况
4.代码：
#include <iostream>
#include <cstdio>
#include <cstdlib> using namespace std; struct FLAT
{
int x[];
int h;
}; int cmp(const void* a,const void* b)
{
FLAT flat1 = *((FLAT *)a);
FLAT flat2 = *((FLAT *)b); return flat1.h - flat2.h;
} int main()
{
//freopen("C://input.txt","r",stdin); int t;
cin >> t; // 0 <= t <= 20 int i,j,k; int n,x,y,max;
while(t--)
{
//1 <= N <= 1000，-20000 <= X, X1[i], X2[i] <= 20000，0 < H[i] < Y <= 20000（i = 1..N）
cin >> n >> x >> y >> max; FLAT *arr_flat = new FLAT[n]; for(i = ; i < n; ++i) cin >> arr_flat[i].x[] >> arr_flat[i].x[] >> arr_flat[i].h;
qsort(arr_flat,n,sizeof(FLAT),cmp); //for(i = 0; i < n; ++i) cout << arr_flat[i].x[0] << " " << arr_flat[i].x[1] << " " << arr_flat[i].h << endl; int m;
for(m = n - ; m >= ; --m)
{
if(y - arr_flat[m].h <= max && x >= arr_flat[m].x[] && arr_flat[m].x[] >= x) break;
}
if(m < )
{
cout << y << endl;
continue;
} //dp
int **dp = new int*[m + ];
for(i = ; i <= m; ++i) dp[i] = new int[]; dp[][] = arr_flat[].h;
dp[][] = arr_flat[].h; for(i = ; i <= m; ++i)
{
for(j = ; j < ; ++j)
{
int flag = ;
for(k = i - ; k >= ; --k)
{
if(arr_flat[i].h - arr_flat[k].h > max) break;
else
{
if(arr_flat[k].x[] <= arr_flat[i].x[j] && arr_flat[k].x[] >= arr_flat[i].x[j])
{
flag = ;
break;
}
}
}
if(flag == )
{
if(arr_flat[i].h < max) dp[i][j] = arr_flat[i].h;
else dp[i][j] = -;
}
else
{
if(dp[k][] == - && dp[k][] == -) dp[i][j] = -;
else if(dp[k][] == -) dp[i][j] = dp[k][] + (arr_flat[i].h - arr_flat[k].h) + (arr_flat[k].x[] - arr_flat[i].x[j]);
else if(dp[k][] == -) dp[i][j] = dp[k][] + (arr_flat[i].h - arr_flat[k].h) + (arr_flat[i].x[j] - arr_flat[k].x[]);
else
{
int temp1 = dp[k][] + (arr_flat[i].h - arr_flat[k].h) + (arr_flat[i].x[j] - arr_flat[k].x[]);
int temp2 = dp[k][] + (arr_flat[i].h - arr_flat[k].h) + (arr_flat[k].x[] - arr_flat[i].x[j]);
dp[i][j] = temp1 < temp2 ? temp1 : temp2;
}
}
}
} if(dp[m][] == -) cout << dp[m][] + (arr_flat[m].x[] - x) + (y - arr_flat[m].h) << endl;
else if(dp[m][] == -) cout << dp[m][] + (x - arr_flat[m].x[]) + (y - arr_flat[m].h) << endl;
else
{
int temp1 = dp[m][] + (arr_flat[m].x[] - x) + (y - arr_flat[m].h);
int temp2 = dp[m][] + (x - arr_flat[m].x[]) + (y - arr_flat[m].h);
cout << (temp1 < temp2 ? temp1 : temp2) << endl;
} for(i = ; i <= m; ++i) delete [] dp[i];
delete [] dp; delete [] arr_flat;
} return ;
}