poj1661-这题目简单dp但是要考虑情况比较多，wa了n次死在了自己定义的无穷大下面
题目大意：
这个是中文的，就不用解释了，有个游戏叫是男人就下100层，就是这个游戏哈。。。
算法分析：
仔细分析发现，其实就是从第一个点开始，由于题目说肯定有解，不会摔死，所以要么向左走，要么向右走，其中至少一个有解。
到下一层，同样要么左走要么右走，其实就是两种状态。那么我们每次只需要求这两种状态的最小值既可。
状态方程：
对于每一层的两个点，
edge[i].min1 = Min(edge[i].x1 - edge[j].x1 + edge[j].min1, edge[j].x2 - edge[i].x1 + edge[j].min2);//左边的点，落到下一层j时，要么左走要么右走，求最小值给它
edge[i].min2 = Min(edge[i].x2 - edge[j].x1 + edge[j].min1, edge[j].x2 - edge[i].x2 + edge[j].min2);//右边的点同样。
注意j不一定存在，因为并不是每次都能够落到板子上，要特殊考虑。
此题不通过时我考虑了一下几种情况，然后修改程序。
1、题目给出的x是不是已经是左边小右边大了，这里我做了比较（未验证）
2、计算到最后剩上面一个点的时候，要考虑直接落到地上的情况，那么时间就是Y
3、考虑在下落过程中，没有落到板子上，分两种情况，一种是落到地上，那么此时min可以设为0（之所以设为0，是因为垂直落下的时间肯定是Y，只需要计算水平时间即可，所以直接落地，没摔死的就是0），另一种情况就是摔死了，那么此条路不通，min赋值无穷大
考虑到这几点，按说是应该能ac了，我还是wa。知道看到discuss给的测试用例，我试了一下，发现程序一个bug那就是我定义无穷大inf为0x7FFFFFFF，由于这个值几乎接近int的最大值，那么在加一点点就会溢出，导致直接变成负的了，所以在定义无穷大的时候一定要考虑这个无穷大会不会还加其他值，会不会溢出。这里谨记。。。。
另外还有一点，这里动态规划要从下往上计算，这个就是dp必须有的特性：无后效性以及重叠子问题性。也就倒推。。。。实际上dp就是递推，只不过有两种方向。
由于此题纠结了几个小时，还是好好总结一下。
下面是代码：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define inf 0x3FFFFFFF//一直wa竟然死在了这个值上面，不能太大啊，否则超出int范围了，一开始定义为7fffffff。
#define Min(a,b) (a<b?a:b)
#define Max(a,b) (a>b?a:b)
#define nMax 1010
int N,X,Y,MAX;
struct EDGE
{
int x1,x2,h,min1,min2;//min1表示由左边点往下落时最小的时间，min2是从右边滑落时最小的时间
}edge[nMax];
int cmp(const void *a, const void *b)
{
struct EDGE *c = (struct EDGE *)a;
struct EDGE *d = (struct EDGE *)b;
return c->h - d->h;
}
int main()
{
int t;
int x1,x2;
scanf("%d", &t);
while (t --)
{
scanf("%d %d %d %d", &N, &X, &Y, &MAX);
for (int i = 0; i < N; ++ i)
{
scanf("%d %d %d", &x1, &x2, &edge[i].h);
//一直不过，不知道x1和x2是不是左边小右边大，这里做了反正没错
edge[i].x1 = Min(x1, x2);
edge[i].x2 = Max(x1, x2);
}
qsort(edge, N, sizeof(edge[0]), cmp);
edge[0].min1 = 0;
edge[0].min2 = 0;
for (int i = 1; i < N; ++ i)
{
//left
bool flag = false;
for (int j = i - 1; j >= 0; -- j)
{
if (edge[i].h - edge[j].h <= MAX && edge[i].x1 >= edge[j].x1 && edge[i].x1 <= edge[j].x2)
{
flag = true;
edge[i].min1 = Min(edge[i].x1 - edge[j].x1 + edge[j].min1, edge[j].x2 - edge[i].x1 + edge[j].min2);
break;
}
else if(edge[i].h - edge[j].h > MAX)
{
break;
}
}
if (!flag)//走到这里表示没有掉到板子上，直接落到地上了。那么存在两种情况，要么摔死，这条路不可走，要么直接到达地面。
{
if (edge[i].h <= MAX)
{
edge[i].min1 = 0;
}
else//摔死了，此路不通
edge[i].min1 = inf;
}
//right
flag = false;
for (int j = i - 1; j >= 0; -- j)
{
if (edge[i].h - edge[j].h <= MAX && edge[i].x2 >= edge[j].x1 && edge[i].x2 <= edge[j].x2)
{
flag = true;
edge[i].min2 = Min(edge[i].x2 - edge[j].x1 + edge[j].min1, edge[j].x2 - edge[i].x2 + edge[j].min2);
break;
}
else if(edge[i].h - edge[j].h > MAX)
{
break;
}
}
if (!flag)//走到这里表示没有掉到板子上，直接落到地上了。那么存在两种情况，要么摔死，这条路不可走，要么直接到达地面。
{
if (edge[i].h <= MAX)
{
edge[i].min2 = 0;
}
else//摔死了，此路不通
edge[i].min2 = inf;
}
}
bool flag = false;
for (int i = N - 1; i >= 0; -- i)//题目中说肯定有解，这里不必考虑落不到板子上或者摔死的情况，只需要考虑直接落地的情况即可
{
if (X >= edge[i].x1 && X <= edge[i].x2)
{
flag = true;
printf("%d\n", Y + Min(X - edge[i].x1 + edge[i].min1, edge[i].x2 - X + edge[i].min2));
break;
}
}
if (!flag)//不经过任何板，直接落地
{
printf("%d\n", Y);
}
}
return 0;
}