NOIP2013原题
貌似官方数据都是一模一样的
以前写过竟然毫无印象？
考场上自己瞎JB推结论
显然，如果连续的两端区间可以左边区间减 k 次，右边区间也减 k 次
那么把两个区间合并起来一起减 k 次一定是更优的
所以先考虑把整个区间拿来减几次，显然最多减的次数就是整个区间的最小值
然后此时最小值已经为零了，以最小值的位置分成左右两个区间继续同样处理就好了
如果每个区间都扫一遍最小值复杂度可以卡成 $O(n^2)$，（单调序列）
所以区间最小值容易想到ST表
然后复杂度 O(n) （每个位置对最小值只产生一次贡献）
话说官方数据 $O(n^2)$ 也能过....
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> using namespace std; typedef long long ll; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<‘0‘||ch>‘9‘) { if(ch==‘-‘) f=-1; ch=getchar(); } while(ch>=‘0‘&&ch<=‘9‘) { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=2e5+7; int n,a[N],pos[N][27],Log[N]; ll ans; void pre()//预处理ST表 { Log[0]=-1; for(int i=1;i<=n;i++) Log[i]=Log[i>>1]+1; for(int i=1;i<=n;i++) pos[i][0]=i; for(int i=1;(1<<i)<=n;i++) for(int j=1;j+(1<<(i-1))<=n;j++) { if(a[ pos[j][i-1] ]>a[ pos[j+(1<<(i-1))][i-1] ]) pos[j][i]=pos[j+(1<<(i-1))][i-1]; else pos[j][i]=pos[j][i-1]; } } inline int query(int l,int r)//区间求最小值 { int k=Log[r-l+1]; if(a[ pos[l][k] ]>a[ pos[r-(1<<k)+1][k] ]) return pos[r-(1<<k)+1][k]; return pos[l][k]; } void f(int l,int r,int tot)//递归处理左右区间,tot是当前已经进行的操作次数 { if(l>r) return; int t=query(l,r); ans+=a[t]-tot; f(l,t-1,a[t]); f(t+1,r,a[t]); } int main() { freopen("road.in","r",stdin); freopen("road.out","w",stdout); n=read(); for(int i=1;i<=n;i++) a[i]=read(); pre(); f(1,n,0); cout<<ans<<endl; return 0; }
原文：https://www.cnblogs.com/LLTYYC/p/10073429.html