好久不動題目了，今天動了一題，忒背運，死都TLE，想了想，算法復(fù)雜度沒問題啊，n=100000，nlogn的算法拼1S的RP咋崩潰的。。后來想起了無敵的POJ超級慢速set，無奈，不想改，到處搜有這題的OJ，TOJ上跑了下，10MS。。汗。。下載數(shù)據(jù)數(shù)據(jù)來看了看，就是12組，就是本地debug也不會TLE啊。。沒辦法。。
不發(fā)牢騷了，說說這題的方法吧。
一般的最長遞增字串用n^2做很好做，就是dp[i]=max{dp[j]+1,height[j]<height[i]}，這題可以用單調(diào)隊列做優(yōu)化，但是和普通的單調(diào)隊列不同，要借助平衡樹
首先，我們知道，要維護這樣一個單調(diào)隊列，當(dāng)height[i]<height[j]時，要有dp[i]<dp[j]，否則的話，status{(j,height[j])}這個狀態(tài)以后不會推得最優(yōu)解，可以刪除。這題麻煩就麻煩再height不是個單調(diào)的函數(shù)，隨著i的增大（就是沿著DP方向計算）時，height不能保證也是遞增的，木有辦法，只能維護一個平衡樹那樣的東西。
那么更新過的DP方程就是
dp[i]=dp[j]+1,j為滿足height[j]<height[i]的最后一個元素
然后更新單調(diào)隊列的策略是把當(dāng)前決策加入單調(diào)隊列里，然后往后刪除dp[i]>=dp[j]并且height[i]<height[j]的statue{j}。
每個元素最多入隊一次，出隊一次，所以總得復(fù)雜度o(nlogn)
我是全部用set實現(xiàn)的，輕松好省
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 else31 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