Description
Input
第一行为一个整数N表示战线的总长度。
第二行N个整数，第i个整数表示在位置i放置守卫塔的花费Ai。
Output
共一个整数，表示最小的战线花费值。
Sample Input
2 3 1 5 4 5 6 3 1 2
Sample Output
HINT
1<=N<=10^6,1<=Ai<=10^9
这道题显然是一道dp的题。一眼看去，显然可以令$f_i$表示第$i$个位置放防御塔的费用(先说明一下，为了方便计算，我把序列反向后从左到右计算)，令$w_x=sum_{i=1}^{x}i$，那么显然有：$f_{i}=min{f_j+w_{i-j-1}}+a_{i}$。然而这是个$n^2$的dp方程，那么怎么做呢？翻了翻网上的题解，发现几乎都写了斜率优化。然而xzy神犇告诉我决策单调性可做。
怎么做呢？不难发现对于位置$i$有两个决策$j,k(j<k)$满足$k$比$j$优，那么对于位置大于$i$的位置也满足这个。证明如下：
若对于$j<k$且$f_j+w_{i-j-1}>f_k+w_{i-k-1}$
因为$j<k$，所以对于$x>i$有$w_{x-j-1}-w_{i-j-1}>w_{x-k-1}-w_{i-k-1}$
所以$f_j+w_{x-j-1}>f_k+w_{x-k-1}$
于是我们就可以做了。我们维护一个单调队列，每次先把队首用不到的区间先弹掉，再用队首元素来更新当前答案，最后用这个解来更新后面的解。当我们发现 对于队尾区间的左端点当前解比队列中储存的解更优时，我们可以直接把这个区间给弹掉(想一想，为什么)。这样弹完以后，若队列中已经没有区间，我们就可以将当前解的区间直接加入队列；否则当前解最优的边界就在队尾的区间中，我们需要在这个区间内二分把这一个边界给找出来，然后更改这个区间的右边界并插入区间。
这道题是我练习决策单调性优化dp的第一题，对于新手来说还是有一点难度的。代码如下：
1 #include<iostream> 2 #include<cstdio> 3 #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout) 4 #define maxn 1000010 5 #define INF (1LL<<50) 6 7 using namespace std; 8 typedef long long llg; 9 10 int n,a[maxn],l[maxn],r[maxn],x[maxn],lz,rz; 11 llg f[maxn]; 12 13 int getint(){ 14 int w=0;bool q=0; 15 char c=getchar(); 16 while((c>'9'||c<'0')&&c!='-') c=getchar(); 17 if(c=='-') q=1,c=getchar(); 18 while(c>='0'&&c<='9') w=w*10+c-'0',c=getchar(); 19 return q?-w:w; 20 } 21 22 inline llg sum(int j,int i){//用j决策来更新f[i] 23 return f[j]+((llg)(i-j)*(i-j-1)>>1); 24 } 25 26 int main(){ 27 File("a"); 28 n=getint(); 29 for(int i=n;i;i--) a[i]=getint(),f[i]=INF; 30 f[1]=a[1]; f[n+1]=INF; 31 l[rz]=2,r[rz]=n+1,x[rz++]=1;//第一个解需要先处理好 32 for(int i=2;i<=n+1;i++){ 33 while(r[lz]<i && lz<rz) lz++;//更新当前解 34 f[i]=sum(x[lz],i)+a[i];//从队尾弹掉没有当前解优的区间 35 while(rz>lz && sum(i,l[rz-1])<=sum(x[rz-1],l[rz-1])) rz--;//修改并插入 36 if(lz==rz) l[rz]=i+1,r[rz]=n+1,x[rz++]=i;//在队尾区间内二分 37 else{ 38 int ll=l[rz-1],rr=r[rz-1]+1,mid,xx=x[rz-1];//修改并插入 39 while(ll!=rr){ 40 mid=ll+rr>>1; 41 if(sum(i,mid)<=sum(xx,mid)) rr=mid; 42 else ll=mid+1; 43 } 44 r[rz-1]=ll-1; l[rz]=ll,r[rz]=n+1,x[rz++]=i;//修改并插入 45 } 46 } 47 printf("%lld",min(f[n],f[n+1])); 48 return 0; 49 }
UPD：斜率优化做法：
其实这个式子可以推一推。由于$w_x=frac{x(x+1)}{2}$，所以有：$f_i=min{ f_j+frac{(i-j)(i-j-1)}{2} }+a_i$
于是对于某一个$j$，有$2f_i-i^2+i-2a_i=2f_j+j^2+j-2ij$
这就是个很显然的斜率式了。由于$i$、$j$单增，用一个单调队列维护下凸包即可。
代码如下：
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout) 7 #define maxn 1000010 8 9 using namespace std; 10 typedef long long llg; 11 12 struct data{ 13 llg x,y; 14 }s[maxn]; 15 int n,a[maxn],d[maxn],l,r; 16 llg f[maxn]; 17 18 int getint(){ 19 int w=0;bool q=0; 20 char c=getchar(); 21 while((c>'9'||c<'0')&&c!='-') c=getchar(); 22 if(c=='-') c=getchar(),q=1; 23 while(c>='0'&&c<='9') w=w*10+c-'0',c=getchar(); 24 return q?-w:w; 25 } 26 27 llg ji(int x){return (llg)x*(llg)x;} 28 double xie(data x,data y){ 29 if(x.x==y.x) return 1e100; 30 return (double)(y.y-x.y)/(double)(y.x-x.x); 31 } 32 33 int main(){ 34 File("a"); 35 n=getint(); 36 for(int i=n;i;i--) a[i]=getint(); 37 f[1]=a[1]; s[1].x=1; s[1].y=1+2*f[1]+1; 38 l=r=1; d[1]=1; 39 for(int i=2;i<=n+2;i++){ 40 while(l<r && xie(s[d[l]],s[d[l+1]])<=(i<<1)) l++; 41 f[i]=f[d[l]]+a[i]+(ji(i-d[l])-(i-d[l]))/2; 42 s[i].x=i; s[i].y=ji(i)+2*f[i]+i; 43 while(l<r && xie(s[d[r-1]],s[d[r]])>=xie(s[d[r]],s[i])) r--; 44 d[++r]=i; 45 } 46 printf("%lld",min(f[n],f[n+1])); 47 return 0; 48 }