題目鏈接：https://vjudge.net/problem/HDU-3507

?

Print Article

Time Limit: 9000/3000 MS (Java/Others)????Memory Limit: 131072/65536 K (Java/Others)
Total Submission(s): 14899????Accepted Submission(s): 4648

Problem Description Zero has an old printer that doesn't work well sometimes. As it is antique, he still like to use it to print articles. But it is too old to work for a long time and it will certainly wear and tear, so Zero use a cost to evaluate this degree.
One day Zero want to print an article which has N words, and each word i has a cost Ci to be printed. Also, Zero know that print k words in one line will cost

M is a const number.
Now Zero want to know the minimum cost in order to arrange the article perfectly.

?

Input There are many test cases. For each test case, There are two numbers N and M in the first line (0 ≤ n ≤?500000, 0 ≤ M ≤ 1000). Then, there are N numbers in the next 2 to N + 1 lines. Input are terminated by EOF.

?

Output A single number, meaning the mininum cost to print the article.

?

Sample Input 5 5 5 9 5 7 5

?

Sample Output 230

?

Author Xnozero

?

Source 2010 ACM-ICPC Multi-University Training Contest（7）——Host by HIT

?

Recommend zhengfeng

?

?

題意：

給出一段字符串，每個(gè)位置上的字符都有其相應(yīng)的價(jià)值Ci。將字符串分成若干子串，且每個(gè)子串的價(jià)值為sigma(Ci)^2+M，i的范圍為區(qū)間的范圍。問(wèn)怎樣分割能得到最小的價(jià)值？

?

題解：

動(dòng)態(tài)規(guī)劃問(wèn)題，設(shè)dp[i]為前i個(gè)字符的最小價(jià)值。再設(shè)sum[i]為前i個(gè)字符的價(jià)值前綴和。

可得：dp[i] = min( dp[j] + (sum[i]-sum[j])^2 + M ) ) ， 其中 0<=k<=i-1。

整理：dp[i] = min( dp[j] + sum[i]^2 + sum[j]^2 - 2*sum[i]*sum[j] + M )， 其中 0<=j<=i-1。

最直接的做法是枚舉j，求得最小值。但是此題n的范圍為5e5，O（n^2）肯定超時(shí)了，所以要借用斜率優(yōu)化，其方法是盡量排除掉那些不可能取得最優(yōu)值的點(diǎn)，縮小狀態(tài)轉(zhuǎn)移的范圍。推理如下：

?

1.如果 k<j，假設(shè)dp[i]在j處取得的值比k處取得的值要小，即更優(yōu)，那么就有：

dp[j] + sum[i]^2 + sum[j]^2 - 2*sum[i]*sum[j] + M <?dp[k] + sum[i]^2 + sum[k]^2 - 2*sum[i]*sum[k] + M，

整理得：[ (dp[j] + sum[j]^2) - (dp[k] + sum[k]^2) ] / ( 2*sum[j] - 2*sum[k] ) < sum[i]。

觀察等式右邊，可以看出這是一個(gè)斜率表達(dá)式。

我們?cè)O(shè) yj =?dp[j] + sum[j]^2， xj =?2*sum[j] ，那么上式就變?yōu)?#xff1a;( yj - yk ) / ( xj - xk ) < sum[i] 。

可知 ( yj - yk ) / ( xj - xk ) 就是直線 j---k 的斜率g[j,k]。

所以：當(dāng)k<j，且j比k更優(yōu)時(shí)， g[j,k] < sum[i]。而且，因?yàn)閟um[i]遞增，所以j比k更優(yōu)的結(jié)論，對(duì)于i以后的位置也合適。……結(jié)論1（此結(jié)論用于求出dp[i]的最優(yōu)轉(zhuǎn)移狀態(tài)）

?

2.當(dāng)k<j<i時(shí)， 如果g[i,j] <= g[j,k]時(shí)， j可以直接排除。 ………………結(jié)論2（此結(jié)論用于維護(hù)隊(duì)列）

1) 當(dāng)g[i,j] < sum[i]時(shí)， i比j更優(yōu)， 所以排除j。

2) 當(dāng)g[i,j] >= sum[i] 時(shí)， g[j, k] >= sum[i]，表明k比j更優(yōu)，所以排除j。

?

3.綜上：只需維護(hù)一個(gè)隊(duì)列，其兩個(gè)相鄰元素間所形成直線的斜率單調(diào)遞增。

?

注意：

判斷不等式的時(shí)候，由于避免整除除法的問(wèn)題，把除法判斷改成了乘法判斷，但是要特別注意，移項(xiàng)是否為負(fù)數(shù)，如果為負(fù)數(shù)，那么不等式的方向就會(huì)發(fā)生變化。

?

?

代碼如下：

1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <vector> 6 #include <cmath> 7 #include <queue> 8 #include <stack> 9 #include <map> 10 #include <string> 11 #include <set> 12 using namespace std; 13 typedef long long LL; 14 const int INF = 2e9; 15 const LL LNF = 9e18; 16 const int mod = 1e9+7; 17 const int MAXM = 1e5+10; 18 const int MAXN = 5e5+10; 19 20 int dp[MAXN], sum[MAXN]; 21 int q[MAXN]; 22 int n, M; 23 24 int getUp(int i, int j) 25 { 26 return (dp[i]+sum[i]*sum[i]) - (dp[j]+sum[j]*sum[j]); 27 } 28 29 int getDown(int i, int j) 30 { 31 return 2*(sum[i]-sum[j]); 32 } 33 34 int getDp(int i, int j) 35 { 36 return dp[i] = dp[j] + (sum[i]-sum[j])*(sum[i]-sum[j]) + M; 37 } 38 39 int main() 40 { 41 while(scanf("%d%d", &n, &M)!=EOF) 42 { 43 sum[0] = 0; 44 for(int i = 1; i<=n; i++) 45 scanf("%d", &sum[i]), sum[i] += sum[i-1]; 46 47 dp[0] = 0; 48 int head = 0, tail = 0; 49 q[tail++] = 0; 50 for(int i = 1; i<=n; i++) 51 { 52 //以下為尋找最優(yōu)的轉(zhuǎn)移狀態(tài)。由于除法改成了乘法，所以順序不能任意，否則不等號(hào)方向會(huì)改變。 53 while(head+1<tail && getUp(q[head+1], q[head])<sum[i]*getDown(q[head+1], q[head])) head++; 54 dp[i] = getDp(i, q[head]); 55 //以下為維護(hù)隊(duì)列 56 while(head+1<tail && getUp(i, q[tail-1])*getDown(q[tail-1], q[tail-2])<= 57 getUp(q[tail-1], q[tail-2])*getDown(i, q[tail-1]) ) tail--; 58 q[tail++] = i; 59 } 60 61 printf("%d\n", dp[n]); 62 } 63 } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/DOLFAMINGO/p/8177150.html

與50位技術(shù)專(zhuān)家面對(duì)面20年技術(shù)見(jiàn)證，附贈(zèng)技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的HDU3507 Print Article —— 斜率优化DP的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。