本題有(O(N))的優秀做法,但是因為在考場上不一定能想到,就來分享一種(O(Nlog_2N))的做法.雖然有點慢,但是可以過.
前置芝士
- 線段樹:提高組及以上必備内容,不會的同學可以學習一下.
具體做法
隻要會線段樹就珂以了,是不是很簡單.
先考慮貪心,連續的一定是一次去掉,不可能分成多次去取.
于是答案就是每一行連續的段數之和.
如圖,第一行為(1)段,第二行(2)段,第三行(2)段,第四行為(1)段,是以答案就是(1+2+2+1=6).然後再考慮怎麼去算出每一行的段數,如果暴力去求肯定是會T的需要(O(N^2))的時間複雜度,好像也沒有什麼其他的快速求法,于是再考慮分治,沒一次将最下方的若幹個完整的一行去掉後就将問題分為若幹個子問題,暴力的方法就可以跑過更多的點了,但還是可能被一些特殊的資料卡掉.
如這樣一個資料,每一次查找目前區間最低的高度需要(O(N))的時間複雜度,最終的時間複雜度就會退化成(O(N^2)).于是可以用線段樹優化.時間複雜度就是(O(Nlog_2N))(大概).
代碼
#include<bits/stdc++.h>
#define rap(i,first,last) for(int i=first;i<=last;++i)
//線段樹标準define
#define Lson (now<<1)
#define Rson (now<<1|1)
#define Middle ((left+right)>>1)
#define Left Lson,left,Middle
#define Right Rson,Middle+1,right
#define Now nowleft,nowright
using namespace std;
const int maxN=5e5+7;
const int INF=123123123;//一個極大值
int N;
int tree[maxN*4];
int arr[maxN];
void PushUp(int now)//查詢區間最大值
{
tree[now]=min(tree[Lson],tree[Rson]);
}
void Build(int now=1,int left=1,int right=N)//建樹
{
if(left==right)
{
tree[now]=arr[left];
return;
}
Build(Left);
Build(Right);
PushUp(now);
}
//不需要修改
int Query(int nowleft,int nowright,int now=1,int left=1,int right=N)//查詢區間最小值
{
if(right<nowleft||nowright<left)return INF;
if(nowleft<=left&&right<=nowright)
{
return tree[now];
}
return min(Query(Now,Left),Query(Now,Right));
}
int QueryPlace(int nowleft,int nowright,int m,int now=1,int left=1,int right=N)
//查詢區間下一個最小值的位置,m為最小值
{
if(right<nowleft||nowright<left)return INF;
if(left==right)
{
if(tree[now]==m)
return left;
return INF;
}
int result=INF;
if(tree[Lson]<=m)//如果左區間可能存在就先查找左區間
{
result=QueryPlace(Now,m,Left);
}
if(result!=INF)return result;//存在就傳回
return QueryPlace(Now,m,Right);//不存在查找右區間
}
long long get(int l,int r/*目前的區間*/,int delhigh/*目前減去的高度*/)
{
if(l>r)return 0;
if(l==r)return arr[l]-delhigh;//l=r時就為目前剩餘高度
int minhigh=Query(l,r);
int now=l-1,place;
if(arr[l]==minhigh)now++;//為了防止陷入死循環
long long result=(minhigh-delhigh);//先将最下方可以取的部分直接取掉
while(1)//通過線段樹将每一段區間找出并繼續加上答案
{
place=QueryPlace(now+1,r,minhigh);
if(place==INF)break;//如果沒有下一個位置就退出
result+=get(now+1,place-1,minhigh);//有就加上答案
now=place;
}
if(arr[r]==minhigh)//為了防止陷入死循環
result+=get(now+1,r-1,minhigh);
else
result+=get(now+1,r,minhigh);
return result;//傳回答案
}
int main()
{
scanf("%d",&N);//讀入
rap(i,1,N)
scanf("%d",&arr[i]);
Build();//建樹
printf("%lld
",get(1,N,0));//輸出
return 0;
}