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

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

洛谷链接

---

分析

首先给出朴素的方程($s[i]={\sum }_{j=1}^{i}x[j]$)
d p [ i ] = m i n { d p [ j ] + a ( s [ i ] − s [ j ] ) 2 + b ( s [ i ] − s [ j ] ) + c } dp[i]=min\{dp[j]+a(s[i]-s[j])^2+b(s[i]-s[j])+c\} 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])\ge dp[j]+a(s[i]-s[j]{)}^2+b(s[i]-s[j])$$
再进一步得到
$$dp[k]+as[k{]}^2-2as[i]s[k]-bs[k]\ge 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])\ge 2as[i](s[k]-s[j])$$
最后得到
$$\frac{dp[k]-dp[j]}{s[k]-s[j]}+a(s[k]+s[j])\ge 2as[i]+b$$
分析$2as[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]);
}

这篇关于#斜率优化，动态规划#jzoj 2318 洛谷 3628 bzoj 1911 特别行动队的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---