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