#斜率优化，动态规划#jzoj 2318 洛谷 3628 bzoj 1911 特别行动队

本文主要是介绍#斜率优化，动态规划#jzoj 2318 洛谷 3628 bzoj 1911 特别行动队，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

洛谷链接

分析

首先给出朴素的方程( $s[i]=\sum_{j=1}^{i}x[j]$ )
$dp[i]=min\{dp[j]+a(s[i]-s[j])^2+b(s[i]-s[j])+c\}$
然后分析 $k (j < k) 比 j$ 更优时，那么
$dp[k]+a(s[i]-s[k])^2+b(s[i]-s[k])\geq dp[j]+a(s[i]-s[j])^2+b(s[i]-s[j])$
再进一步得到
$dp[k]+as[k]^2-2as[i]s[k]-bs[k]\geq dp[j]+as[j]^2-2as[i]s[j]-bs[j]$
移项后得到
$dp[k]-dp[j]+as[k]^2-as[j]^2-b(s[k]-s[j])\geq 2as[i](s[k]-s[j])$
最后得到
$\frac{dp[k]-dp[j]}{s[k]-s[j]}+a(s[k]+s[j])\geq 2as[i]+b$
分析 $2 a s [i] + b$ 单调递减，所以说维护的是上凸壳，然后就可以 $O (n)$ 解决

代码

#include <cstdio>
#include <cctype>
#define rr register
#define w(x) ((x)*(x))
#define max(a,b) (((a)>(b))?(a):(b))
using namespace std;
int n,s[1000001],q[1000001];
long long a,b,c,dp[1000001];
inline signed iut(){rr int ans=0,f=1; rr char c=getchar();while (!isdigit(c)&&c!='-') c=getchar();if (c=='-') c=getchar(),f=-f;while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();return ans*f;
}
inline double slope(int x,int y){if (s[y]==s[x]) return 1e18;else return 1.0*(dp[y]-dp[x])/(s[y]-s[x])+a*(s[x]+s[y]);
}
signed main(){n=iut(); a=iut(); b=iut(); c=iut();for (rr int i=1;i<=n;++i) s[i]=s[i-1]+iut();for (rr int i=1,head=1,tail=1;i<=n;++i){while (head<tail&&slope(q[head],q[head+1])>=(a*s[i]<<1)+b) ++head;dp[i]=dp[q[head]]+a*w(s[i]-s[q[head]])+b*(s[i]-s[q[head]])+c;while (head<tail&&slope(q[tail-1],q[tail])<slope(q[tail],i)) --tail;q[++tail]=i;}return !printf("%lld",dp[n]);
}