The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

POJ 1661 Help Jimmy 有点麻烦的动态规划 O(n^2)

   蛮麻烦的一个题 但是说白了 也就是一个类似最长上升子序列的东西(可能跳转的跨度大了些) 从底部往上逐层DP,每一层有两个状态 分别求之。小结一下吧 做了这么多动态规划题 我发现 动态规划的实质 居然是穷举 ,囧啊,或者更确切的来说是 带记忆化的穷举!存储加递归应该还是欠妥的,因为毕竟有了最优子结构以后 后效状态便消除了,而且也并没有揭示出DP解法的全局性(如果用更宏观的视角来看待它),即它在求得答案的同时,也获得了其他更多的信息,这些信息不是冗余(redundant 恩GRE高频词),形象的说 应该是在DP之路上,为答案作出贡献的朋友,如果我们换一个问题,也许它们也就成了答案。
   对了,补充一下,我觉得这个题最重要的地方在于,当你找到了一块板刚好能接住从左侧下降的你时,你便不用再考虑更下层的板了,因为你不可能穿墙(板)!
#include<iostream>
#include
<algorithm>
#include
<cstdio>
using namespace std;
#define INF 999999999

struct node
{
    
int x1;
    
int x2;
    
int h;
    
bool operator <(node other)
    
{
        
return h>other.h;
    }

}
a[1005];
int dp[1001][2];


int n,x,y,mh;
int main()
{

    
int t;
    
int i,j,k;
    scanf(
"%d",&t);
    
for(k=1;k<=t;k++)
    
{
        scanf(
"%d%d%d%d",&n,&x,&y,&mh);
        
for(i=1;i<=n;i++)
        
{
            scanf(
"%d%d%d",&a[i].x1,&a[i].x2,&a[i].h);
            dp[i][
0]=dp[i][1]=INF;
        }

        dp[n
+1][0]=dp[n+1][1]=0;
        a[n
+1].x1=-INF;
        a[n
+1].x2=INF;
        sort(a
+1,a+1+n);
        
for(i=n;i>=1;i--)
        
{
            
bool l=false;
            
bool r=false;
            
for(j=i+1;j<=n+1;j++)
            
{
                
if(a[i].h-a[j].h>mh)
                    
break;
                
if(!l&&a[i].x1>=a[j].x1&&a[i].x1<=a[j].x2)
                
{
                    
if(j==n+1) dp[i][0]=0;
                    
else 
                    
{
                        dp[i][
0]=min(dp[i][0],dp[j][0]+a[i].x1-a[j].x1);
                        dp[i][
0]=min(dp[i][0],dp[j][1]+a[j].x2-a[i].x1);
                        l
=true;
                    }

                }

                
if(!r&&a[i].x2>=a[j].x1&&a[i].x2<=a[j].x2)
                
{
                    
if(j==n+1) dp[i][1]=0;
                    
else 
                    
{
                        dp[i][
1]=min(dp[i][1],dp[j][0]+a[i].x2-a[j].x1);
                        dp[i][
1]=min(dp[i][1],dp[j][1]+a[j].x2-a[i].x2);
                        r
=true;
                    }

                }

            }

        }

        
int res=0;
        
for(i=1;i<=n+1;i++)
        
{

            
if(a[i].x1<=x&&x<=a[i].x2&&y>=a[i].h)
            
{
                res
=min(x-a[i].x1+dp[i][0],a[i].x2-x+dp[i][1]);
                
break;
            }



        }

        res
+=y;
        printf(
"%d\n",res);

    }

    
return 0;
}


posted on 2010-03-23 23:50 abilitytao 阅读(1244) 评论(2)  编辑 收藏 引用

评论

# re: POJ 1661 Help Jimmy 有点麻烦的动态规划 O(n^2) 2010-03-24 00:11 schindlerlee

刚瞄了眼pku web board
abilitytao 2010-03-23 23:39:11 Problem 1661

报告写的真快。。。  回复  更多评论   

# re: POJ 1661 Help Jimmy 有点麻烦的动态规划 O(n^2) 2010-03-25 17:18 淘宝皇冠大全

按时间的就暗示的啊  回复  更多评论   


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理