打印文章

一、題意及數據范圍

題目描述
題目大意：輸出N個數字a[N]，輸出的時候可以連續的輸出，每連續輸出一串，它的費用是 “這串數字和的平方加上一個常數M”，求最小的費用。
數據范圍
n<=500000 , m<=1000。

二、解法

基本思路

根據題目，我們可以列出dp[i]=dp[j]+(a[i]-a[j])²+m,其中dp[i]表示i點是最后一段的最后一個數字的最小花費,a[j]是前綴和。但是這個dp式顯然是O(n²)的，我們考慮怎么對它進行優化，化簡得：
dp[i]=dp[j]+a[i]²+a[j]²-2*a[i]*a[j]+m
由于這個dp式在計算時需要a[i]和a[j]的乘積，單調隊列就不能維護了。

斜率優化
半年多沒接觸，都不知道怎么用它了……
接下來有一些玄學推導：
設用j更新比k更優，則：
dp[j]+a[i]²+a[j]²-2*a[i]*a[j]+m<dp[k]+a[i]²+a[k]²-2*a[i]*a[k]
消去同類項：dp[j]+a[j]²-2*a[i]*a[j]<dp[k]+a[k]²-2*a[i]*a[k]
移項：dp[j]-dp[k]+a[j]²-a[k]²<2*a[i]*(a[j]-a[k])
我們設f[j]=dp[j]+a[j]²,f[k]=dp[k]+a[k]²
$\frac{dp[j]?a[k]}{a[j]?a[k]}$<2*a[i]
這個東西……是不是很像斜率
哈！這就是它為什么要叫斜率優化。

具體實現
其實最重要的東西我都講了，我們可以用這個式子結合單調隊列維護凸包，就能過了。
看代碼吧。

#include <cstdio> #define LL long long const LL MAXN = 500005; LL read() {LL x=0,flag=1;char c;while((c=getchar())<'0' || c>'9') if(c=='-') flag=-1;while(c>='0' && c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar();return x*flag; } LL n,m,a[MAXN],q[MAXN],dp[MAXN];LL slope_up(LL j,LL k) {return (dp[j]+a[j]*a[j])-(dp[k]+a[k]*a[k]); } LL slope_down(LL j,LL k) {return 2*a[j]-2*a[k]; } int main() {while(~scanf("%lld %lld",&n,&m)){for(LL i=1;i<=n;i++)a[i]=a[i-1]+read();LL head=1,tail=0;q[++tail]=0;dp[0]=0;for(LL i=1;i<=n;i++){while(head<tail && slope_up(q[head+1],q[head])<=a[i]*slope_down(q[head+1],q[head])) head++;//維護隊首，如上述，當小于時就一定不比q[head+1]優。避免精度問題，使用乘法。 dp[i]=dp[q[head]]+(a[i]-a[q[head]])*(a[i]-a[q[head]])+m;while(head<tail && slope_up(q[tail],q[tail-1])*slope_down(i,q[tail])>=slope_up(i,q[tail])*slope_down(q[tail],q[tail-1])) tail--;//同樣維護凸包，使用乘法。 q[++tail]=i;}printf("%lld\n",dp[n]);} }

注：本篇題解只是斜率優化入門，沒有深究，后面做到難題時再補幾發博客吧

總結

以上是生活随笔為你收集整理的HDU3507打印文章 斜率优化入门的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。