pku3903 最长递增字串的单调性优化

好久不动题目了,今天动了一题,忒背运,死都TLE,想了想,算法复杂度没问题啊,n=100000,nlogn的算法拼1S的RP咋崩溃的。。后来想起了无敌的POJ超级慢速set,无奈,不想改,到处搜有这题的OJ,TOJ上跑了下,10MS。。汗。。下载数据数据来看了看,就是12组,就是本地debug也不会TLE啊。。没办法。。
不发牢骚了,说说这题的方法吧。
一般的最长递增字串用n^2做很好做,就是dp[i]=max{dp[j]+1,height[j]<height[i]},这题可以用单调队列做优化,但是和普通的单调队列不同,要借助平衡树
首先,我们知道,要维护这样一个单调队列,当height[i]<height[j]时,要有dp[i]<dp[j],否则的话,status{(j,height[j])}这个状态以后不会推得最优解,可以删除。这题麻烦就麻烦再height不是个单调的函数,随着i的增大(就是沿着DP方向计算)时,height不能保证也是递增的,木有办法,只能维护一个平衡树那样的东西。
那么更新过的DP方程就是
dp[i]=dp[j]+1,j为满足height[j]<height[i]的最后一个元素
然后更新单调队列的策略是把当前决策加入单调队列里,然后往后删除dp[i]>=dp[j]并且height[i]<height[j]的statue{j}。
每个元素最多入队一次,出队一次,所以总得复杂度o(nlogn)
我是全部用set实现的,轻松好省
 1 # include <cstdio>
 2 # include <set>
 3 using namespace std;
 4 struct node
 5 {
 6    int height,id;
 7    node(int h,int i):height(h),id(i){}
 8    bool operator<(const node &pos) const
 9    {
10        if(height!=pos.height) return height<pos.height;
11        else return id<pos.id;
12    }
13 };
14 set<node> q;
15 int dp[100005];
16 int main()
17 {
18      int n;
19      while(scanf("%d",&n)!=EOF)
20      {
21         q.clear();
22         for(int i=0;i<n;i++)
23         {
24             int t;
25             scanf("%d",&t);
26             set<node>::iterator it=q.lower_bound(node(t,-1));
27             int ans;
28             if(it==q.begin())
29               ans=1;
30             else
31               ans=dp[(--it)->id]+1;
32             it=q.lower_bound(node(t,-1));
33             if(it!=q.end()&&it->height==t) 
34                  it=q.erase(it);
35             while(it!=q.end()&&dp[it->id]<=ans) 
36                  it=q.erase(it);
37             q.insert(node(t,i)); 
38             dp[i]=ans;
39         }
40         printf("%d\n",dp[q.rbegin()->id]);
41      }
42      return 0;
43 }
44 

posted on 2012-02-09 19:33 yzhw 阅读(277) 评论(0)  编辑 收藏 引用 所属分类: DP


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2012年2月>
2930311234
567891011
12131415161718
19202122232425
26272829123
45678910

导航

统计

公告

统计系统

留言簿(1)

随笔分类(227)

文章分类(2)

OJ

最新随笔

搜索

积分与排名

最新评论

阅读排行榜