注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

OI之路,漫漫人生

只为梦想,没有理由

 
 
 

日志

 
 

poj1661Help Jimmy题解  

2014-03-25 21:57:30|  分类: POJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
                                                                帮助JIMMY
                                       BY   LGS
题目大意:一开始JIMMY一定在平台上方,给出N个平台的高度,左端点和右端点。JM下落S需要S秒,遇到平台只能选择往左走到端点,往右走到端点,走S需要S秒。然后继续下落循环,直到落到地面,求一种方案使落地时间最短。输出最短时间。

题解:POJ2374的那题比这题难,那题还要用线段树维护I个平台下方左端点是第几个平台。而这题由于N比较小,直接枚举i-1个平台即可。一开始根据H排序。DP[I][0..1],表示这个平台i左端点和右端点到地面的最小时间。只考虑左端点,右端点类似。
IF i左端点下面无线段{
IF i的高度>maxh,DP[I][0]=MAXX;
            ELSE DP[I][0]=0;
                                          }
 ELSE {
IF i-k的高度>maxh, DP[I][0]=MAXX;
           ELSE DP[I][0]=MIN(DP[K][0]+ABS(L[K]-L[I]),DP[K][1]+ABS(R[K]-L[I]));
             }
总结:DP;
代码:
  • Source Code
  • #include<cstdio>
    #include<algorithm>
    #define maxn 2000
    #define maxx 29999999
    using namespace std;
    int flag,i,j,k,n,x0,y0,ans,maxh,t,m;
    int f[maxn][2];
    struct node{int l,r,h;}a[maxn];
    bool cmp(const node&a,const node&b){return a.h>b.h;}
    int min(int a,int b){return (a>b)?b:a;}
    int main()
    {
     scanf("%d",&t);
     for (k=1;k<=t;k++)
      {
      scanf("%d%d%d%d",&n,&x0,&y0,&maxh);n++;
      for (i=2;i<=n;i++) scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].h);
      a[1].l=x0;a[1].r=x0;a[1].h=y0;
      sort(a+1,a+n+1,cmp);
      for (i=n;i>=1;i--)
           {
           flag=0;
           for (j=i+1;j<=n;j++)
            if (a[j].l<=a[i].l&&a[j].r>=a[i].l){flag=1;break;}
           if (flag==1){
           if (a[i].h-a[j].h>maxh) f[i][0]=maxx;
                else { 
    f[i][0]=min(f[j][0]+a[i].h-a[j].h+a[i].l-a[j].l
               ,f[j][1]+a[i].h-a[j].h+a[j].r-a[i].l);
                     }
                       }
                  else {if (a[i].h>maxh) f[i][0]=maxx;else f[i][0]=a[i].h;}
                     
           flag=0;
            for (j=i+1;j<=n;j++)
            if (a[j].l<=a[i].r&&a[j].r>=a[i].r){flag=1;break;}
           if (flag==1){
           if (a[i].h-a[j].h>maxh) f[i][1]=maxx;
                else { 
    f[i][1]=min(f[j][0]+a[i].h-a[j].h+a[i].r-a[j].l
               ,f[j][1]+a[i].h-a[j].h+a[j].r-a[i].r);
                     }
                       } 
                            else {if (a[i].h>maxh) f[i][1]=maxx;
                                   else f[i][1]=a[i].h;}
    
           }
         ans=min(f[1][0],f[1][1]);
      if (ans>=maxx) printf("-1\n");
                  else printf("%d\n",ans);
      }
    return 0;
    }
  评论这张
 
阅读(5593)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018