无知 无求

0%

poj1661 Help Jimmy

发表于 分类于 ，

题意

是男人就下一百层！ 你有初始的x坐标与高度 下面有n块板子 每个板子都有自己的长度与高度 你下降与在板子上走的速度都是1m/s，你唯一能做的操作是掉落到板子上时候选择向左走还是向右走，问掉到地面的最短时间 保证有解

另外你每次掉落的高度不能超过一个max值，超过就摔死了~

题解

写起来要稍稍复杂一些。。简单来说我的思路是dp[i][j]表示走到第i块板子的边缘所需要的时间，j为0或1，首先把板子按高度排一下，然后对于每块板子看在它之前的板子能不能掉到它上，统计一下走到边缘花的时间，最后遍历找最小即可

实际上问题要稍稍复杂一些。。因为掉落是没办法控制的，也就是说你从边缘掉下去 而下面有板子你就一定会掉上去需要再走到边缘 而不能传过去（ 所以加了一个记录来判断这个问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int MAXN=0x3f3f3f3f;
int dp[1020][2];
struct wal{
    int x[2];
    int h;
    int ans[2];
    int next[2];
};
wal walls[1020];
bool cmp(wal a,wal b){
    return a.h>b.h;
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        int n,x,y,hmax;
        scanf("%d%d%d%d",&n,&x,&y,&hmax);
        for(int i=1;i<=n;++i){
            scanf("%d%d%d",&walls[i].x[0],&walls[i].x[1],&walls[i].h);
        }
        walls[0].x[0]=walls[0].x[1]=x;
        walls[0].h=y;
        sort(walls+1,walls+1+n,cmp);
        memset(dp,MAXN,sizeof(dp));
        dp[0][0]=dp[0][1]=0;
        int ans=MAXN;
        for(int i=0;i<=n;++i){
            walls[i].ans[0]=walls[i].ans[1]=MAXN;
            walls[i].next[0]=walls[i].next[1]=-1;
            for(int j=0;j<i;++j){
                if((walls[j].h-walls[i].h)>hmax){
                    continue;
                }
                if(dp[j][0]!=MAXN&&walls[j].x[0]>=walls[i].x[0]&&walls[j].x[0]<=walls[i].x[1]&&walls[j].next[0]==-1){
                    walls[j].next[0]=i;
                    dp[i][0]=min(dp[i][0],dp[j][0]+walls[j].h-walls[i].h+abs(walls[j].x[0]-walls[i].x[0]));
                    dp[i][1]=min(dp[i][1],dp[j][0]+walls[j].h-walls[i].h+abs(walls[j].x[0]-walls[i].x[1]));
                }
                if(dp[j][1]!=MAXN&&walls[j].x[1]>=walls[i].x[0]&&walls[j].x[1]<=walls[i].x[1]&&walls[j].next[1]==-1){
                    walls[j].next[1]=i;
                    dp[i][0]=min(dp[i][0],dp[j][1]+walls[j].h-walls[i].h+abs(walls[j].x[1]-walls[i].x[0]));
                    dp[i][1]=min(dp[i][1],dp[j][1]+walls[j].h-walls[i].h+abs(walls[j].x[1]-walls[i].x[1]));
                }
            }
            if(walls[i].h<=hmax){
                walls[i].ans[0]=min(walls[i].ans[0],dp[i][0]+walls[i].h);
                walls[i].ans[1]=min(walls[i].ans[1],dp[i][1]+walls[i].h);
            }
        }
        for(int i=0;i<=n;++i){
            if(walls[i].next[0]==-1){
                ans=min(ans,walls[i].ans[0]);
            }
            if(walls[i].next[1]==-1){
                ans=min(ans,walls[i].ans[1]);
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}