斜率优化-征途

斜率优化-征途

---

BZOJ4518
需要自行展开并简化式子。

乘了$m^2$后乱搞就有以下式子：
$ans=m\times \sum _ {i=1} ^ n a _ i^ 2-(\sum_ {i=1}^ na_ i)^2$
发现后面那一项固定
令$dp[i][j]$表示$i$天$j$段路最小的前面那一项，$pre[k]$表示前$k$段路的和
则$dp[i][j]=min(dp[i-1][k]+(pre[j]-pre[k])^2)(i \leq k < j)$
假设$a < b$ 则当$b$更优时会有：
$f[i-1][a]+(pre[j]-pre[a])^2>f[i-1][b]+(pre[j]-pre[b])^2$
得
$\frac {(f[i-1][a]+pre[a]^2)-(f[i-1][b]+pre[b]^2)}{2pre[a]-2pre[b]} < pre[j]$
把$f[i-1][a]+pre[a]^2$看作$Y _a$,$2pre[a]$看作$X _a$
也就是说当$\frac{Y _b-Y _a}{X _b-X _a} < pre[j]$时，选$b$更优
反之则选a更优
现在考虑对于$a,b,c$，当此式子成立时：
$\frac{Y _b-Y _a}{X _b-X _a}>\frac{Y _c-Y _b}{X _c-X _b}$
会发现对于另一个数$k$,
当$\frac{Y _c-Y _b}{X _c-X _b} < pre[k]$时取$c$
当$\frac{Y _b-Y _a}{X _b-X _a} > pre[k]$时取$a$
不存在中间的情况

现在构建一个可能转移到下一天的序列。
而b作为一个“山谷”，没有任何价值。
所以在构建的时候可以，也应该舍掉$b$
这样这道题就构建除出了一个两个点间斜率不断上升的“凸包”
根据上面取$a$比取$b$好的定义化简的结果，我们要找的是斜率第一个大于$pre[j]$的线段的左端点，而我们判断时的$pre[j]$也是在不断上升的
所以斜率比$pre[j]$小的之后肯定用不上了，丢掉就好w
斜率小了就往后搜
这样每个在凸包上的点只会被访问一次，计算一天就只用$O(n)$了

对于每一天，边转移边构建前一天的凸包序列（防止把这一段之后的状态转移进来），做完这天就构造好了前一天的
然而前一天的凸包已经没什么用了

最后把$dp$结果带回原式。

Code:

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long lint;
const int N=3005;
int n,m,qh,qt,pr[N],dp[N],fp[N],que[N*N];

inline lint _x(int x){return pr[x]<<1;}

inline lint _y(int x){return fp[x]+pr[x]*pr[x];}

inline int nxi(){
	int x=0;
	char c;
	while((c=getchar())>'9'||c<'0');
	while(x=x*10+c-48,(c=getchar())>='0'&&c<='9');
	return x;
}

inline int top(int x){
	int a,b;
	while(qt-qh>1&&_y(b=que[qh+1])-_y(a=que[qh])<pr[x]*(_x(b)-_x(a))) ++qh;
	return que[qh];
}

inline bool jdg(int a,int b,int c){
	int x=_x(b),y=_y(b);
	return (x-_x(a))*(_y(c)-y)-(_x(c)-x)*(y-_y(a))>=0;
}

inline void psh(int x){
	while(qt-qh>1&&jdg(que[qt-2],que[qt-1],x)==0) --qt;
	que[qt++]=x;
}

int main(){
	n=nxi(),m=nxi();
	for(int i=1;i<=n;++i) pr[i]=pr[i-1]+nxi();
	for(int i=1;i<=n;++i) fp[i]=pr[i]*pr[i];
	for(int i=2;i<=m;++i){
		que[qh=(qt=1)-1]=i-1;
		for(int j=i;j<=n;++j){
			int k=top(j);
			dp[j]=fp[k]+(pr[j]-pr[k])*(pr[j]-pr[k]);
			psh(j);
		}
		memcpy(fp,dp,sizeof(dp));
	}
	printf("%d\n",m*dp[n]-pr[n]*pr[n]);
	return 0;
}