bzoj1109: [POI2007]堆积木Klo-白红宇的个人博客

bzoj1109: [POI2007]堆积木Klo

发布日期：2021-08-17 20:35:04 浏览次数：1 分类：技术文章

本文共 792 字，大约阅读时间需要 2 分钟。

为啥我考虑了DP考虑了cdq就没考虑考虑两个合起来哩

这个题首先一看就很乱搞。。。

容易想到自己的值减去下标。。。

那么当前位置DP的话能继承什么呢？

首先位置要在自己前面，然后值要比自己小，还有，因为它前面的积木被推了它受影响我也受影响，我们之间的积木被推了我受影响它没事，所以它距离正确位置的距离要比我要小才行，当然假如这个距离是负数就不能到达，去掉这个状态。

写出来就是j<i&&a[j]<a[i]&&j-a[j]<=i-a[i]三维偏序但是其实吧，假如满足后两个，前面那个也肯定满足的。。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;int s[110000];int lowbit(int x){ return x&-x;}void change(int x,int k){ while(x<=100010) { s[x]=max(s[x],k); x+=lowbit(x); }}int getmax(int x){ int ret=0; while(x>0) { ret=max(ret,s[x]); x-=lowbit(x); } return ret;}struct node{ int x,y;}a[110000];bool cmp(node n1,node n2){ return n1.x==n2.x?n1.y

转载于:https://www.cnblogs.com/AKCqhzdy/p/9564093.html

转载地址：https://blog.csdn.net/weixin_30867015/article/details/96630037 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：Ajax原理与图解

下一篇：Android网络多线程断点续传下载(转)

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章