BZOJ 1010
第二道斜率优化，对斜率优化有了新的理解。开心（大雾
这题的题面其实就是在说 斜率优化！斜率优化！斜率优化！
好吧就是道裸题
我们考虑更新f[i]时选择的节点
如果k比j更优
则有：
f[j]+(j-i+sum[i]-sum[j]-L)^2<f[k]+(L+k-i+sum[i]-sum[k]-L)^2
f[j]+(sum[i]-sum[j])^2-2*(i-j+L)*(sum[i]-sum[j])+(i-j+L)^2<f[k]+(sum[i]-sum[k])^2+2*(i-k+L)*(sum[i]-sum[k])+(i-k+L)^2
令t1=i-j+L,t2=i-k+L;
f[j]+(sum[i]-sum[j])^2-2*t1*(sum[i]-sum[j])+t1^2<f[k]+(sum[i]-sum[k])^2-2*t2*(sum[i]-sum[k])+t2^2
f[j]-f[k]+(sum[i]-sum[j])^2-(sum[i]-sum[k])^2+t1^2-t2^2<2*sum[i]*(sum[k]-sum[j]+k-j)
f[j]-f[k]+(sum[i]-sum[j])^2-(sum[i]-sum[k])^2+t1^2-t2^2)/(2*sum[k]-sum[j]+k-j)<sum[i]
。。别看这个公式很烦，其实你如果用Sum[i]去表示sum[i]+i的话很方便，只是这里我写的严谨了点
嗯、、Sum[i]表示的话，公式如下
(f[j]-f[k]+(sum[j]+l)^2+(sum[k]+l)^2)/(2*(sum[k]-sum[j])<sum[i]
好了就是这样
考虑这个东西是个斜率式子，我们要求最小值，所以斜率不可能递减
为什么？因为递减的话你还不如直接从上一个位置更新过来
所以我们可以根据这个性质，维护一个下凸壳
顺便一说，如果是要最大值，则要维护上凸壳
补：
突然发现忘记放代码了。。。。
#include <iostream> #include <cstdio> #include <cmath> #include <algorithm> #include <queue> #include <string> #include <map> #include <set> #include <cstring> #include <ctime> #include <vector> #define inf 1e9 #define eps 1e-9 #define iter multiset<ll>::iterator #define ll long long #define maxn 20010 #define For(i,j,k) for(ll i=j;i<=k;i++) #define Dow(i,j,k) for(ll i=k;i>=j;i--) using namespace std; inline void read(ll &tx){ ll 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*10+ch-'0';ch=getchar();} tx=x*f; } inline void write(ll x){ if (x<0) putchar('-'),x=-x; if (x>=10) write(x/10); putchar(x+'0'); } inline void writeln(ll x){write(x);puts("");} ll n,l,a[100001],q[100001],L,R,f[100001]; inline ll sqr(ll x){return x*x;} inline double get(ll y,ll x) { return (double)(f[x]-f[y]+sqr(a[x]+l)-sqr(a[y]+l))/(2.0*(a[x]-a[y])); } int main() { read(n);read(l);l++; For(i,1,n) read(a[i]); For(i,1,n) a[i]+=a[i-1]+1; L=R=1;q[1]=0; For(i,1,n) { while(L<R&&get(q[L],q[L+1])<=a[i]) L++; f[i]=f[q[L]]+sqr(a[i]-a[q[L]]-l); while(L<R&&get(q[R-1],q[R])>get(q[R],i)) R--; q[++R]=i; } writeln(f[n]); }
