BZOJ1010

【分析】首先直接求dp方程为:dp[i] = MIN{ dp[j]+(sum[i]-sum[j]-(1+L))^2 }(j < i);

直接求n^2必然超时，这是第一个斜率DP：

1.证明决策单调性

设在状态i处的k决策优与j决策，即

dp[k]+(f[i]-f[k]-c)^2<=dp[j]+(f[i]-dp[j]-c)^2

对于后的某状态t,dp[t]=dp[i]+v;

要证明dp[k]+(f[t]-f[k]-c)^2<=dp[j]+(f[t]-f[j]-c)^2

只要证

dp[k]+(f[i]+v-f[k]-c)^2<=dp[j]+(f[i]+v-f[j]-c)^2

只要证

dp[k]+(f[i]-f[k]-c)^2+2*v*(f[i]-f[k]-c)+v^2<=dp[j]+(f[i]-f[j]-c)^2+2*v*(f[i]-f[j]-c)+v^2

只要证

2*v*(f[i]-f[k]-c)<=2*v*(f[i]-f[j]-c)

即f[k]>=f[j]（显然）

证明完毕

2.求斜率方程，一般化成左边为j,k,右边为i的方程

因为dp[k]+(f[i]-f[k]-c)^2<=dp[j]+(f[i]-f[j]-c)^2

展开

dp[k]+f[i]^2-2*f[i]*(f[k]+c)+(f[k]+c)^2<=dp[j]+f[i]^2-2*f[i]*(f[j]+c)+(f[j]+c)^2

即

dp[k]-2*f[i]*(f[k]+c)+(f[k]+c)^2<=dp[j]-2*f[i]*(f[j]+c)+(f[j]+c)^2

即(dp[k]+(f[k]+c)^2-dp[j]-(f[j]+c)^2)/2*(f[k]-f[j])<=f[i]

3.则(dp[k]+(f[k]+c)^2-dp[j]-(f[j]+c)^2)/2*(f[k]-f[j])就是斜率方程，然后使用单调队列维护凸包；

令f(k,j)为斜率方程

队首：当f(q[x+1],q[x]) <= f[i]时说明q[x+1]比q[x]更优，所以删掉q[x];

队尾：当f(i,q[y]) < f(q[y-1],q[y])时，说明i比q[y]更优，删掉q[y];

【AAC CODE】76ms

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXN = 50000+10, MAXIN = 10000;
char buf[MAXIN], *ps = buf, *pe = buf+1;
inline void rnext(){
	if(++ps == pe) pe = (ps = buf)+fread(buf,sizeof(char),sizeof(buf)/sizeof(char),stdin);
}
template <class T>
inline bool in(T &ans)
{
	ans = 0;
	T f = 1;
	if(ps == pe) return false;
	do{ rnext(); if('-' == *ps) f = -1;} while(!isdigit(*ps) && ps != pe);
	if(ps == pe) return false;
	do{ ans = (ans<<1)+(ans<<3)+*ps-48;rnext();}while(isdigit(*ps) && ps != pe);
	ans *= f;
	return true;
}

LL s[MAXN],c,dp[MAXN];
inline LL f(int k, int j)
{
	return (dp[k]-dp[j]+2*s[k]*c-2*s[j]*c+s[k]*s[k]-s[j]*s[j]);
}
inline LL down(int k, int j)//化除法为乘法，提高精度和时间效率
{
	return (s[k]-s[j])<<1;
}
int q[MAXN];
int main()
{
#ifdef SHY
	freopen("d:\\1.txt", "r", stdin);
#endif
	int n;
	while(in(n))
	{
		in(c);
		int a;
		c++;
		repe(i,1,n) in(a), s[i] = s[i-1]+a;
		repe(i,1,n) s[i] += i;
		int x = 1, y = 1;
		repe(i,1,n)
		{
			while(x < y && f(q[x+1],q[x]) <= s[i]*down(q[x+1],q[x])) x++;
			int j = q[x];
			dp[i] = dp[j]+(s[i]-s[j]-c)*(s[i]-s[j]-c);
			while(x < y && f(q[y],i)*down(q[y-1],q[y]) <= f(q[y-1],q[y])*down(q[y],i)) y--;
			q[++y] = i;
		}
		printf("%lld\n",dp[n]);
	}
	return 0;
}