【分析】首先直接求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; }