[HDU3507] Print Article

斜率优化qwq

题意

一个人要用 $ n(0\le n\le 500000) $ 个单词打一篇文章。一个单词有一个价值 $ C_i $,一个文章可以分成若干段,每一段消耗价值 $ (\sum_{i=1}^kC_i)^2+M $ ,其中 $ M $是常数。问如何安排单词打法,使得消耗的价值最小?

思路

斜率优化,还是写一下吧(下一道题就不详述过程了)。

设 $ s_n = \sum_{i = 1}^{n}{C_i} $ 。

现有朴素dp式子 $ f_i = min_{j < i}\{f_j + (s_i - s_j) ^ 2 + M\} $ 。

整理可得 $ f_i = s_i^2 + M + min_{j < i}\{f_j + s_j^2 - 2 s_i s_j \}$。

两个决策j,k,$ j < k $,j比k优,则设$ A_j = f_j + s_j^2 , B_j = 2 s_j$。

可得 $ s_i < \frac{A_k - A_j}{B_k - B_j} $。

则平面直角坐标系上点 $ (B_j,A_j) \; (B_k,A_k) $的连线斜率大于 $ s_i $。

构成一个下凸包。

由于决策是单调的,于是单调队列维护。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <cstdio>
#include <cstring>
#include <cctype>
inline int getint()
{
int r = 0,s = 1;char c = getchar();for(;!isdigit(c);c = getchar()) if(c == '-') s = 0;
for(;isdigit(c);c = getchar()) r = (((r << 2) + r) << 1) + (c ^ '0');return s ? r : -r;
}
const int N = 500050;
int c[N],s[N],n,m,x[N],y[N],dp[N];
int Q[N],h = 0,t = 0;
inline int ufrac(int i,int j){return dp[j] - dp[i] + s[j] * s[j] - s[i] * s[i];}
int main()
{
while(~scanf("%d%d",&n,&m))
{
s[0] = dp[0] = 0;h = t = 0;
for(int i = 1;i <= n;i++) x[i] = 2 * (s[i] = s[i - 1] + (c[i] = getint()));
Q[t++] = 0;
for(int i = 1;i <= n;i++)
{
while(h + 1 < t && ufrac(Q[h],Q[h + 1]) <= s[i] * (x[Q[h + 1]] - x[Q[h]])) h++;
dp[i] = m + dp[Q[h]] + (s[i] - s[Q[h]]) * (s[i] - s[Q[h]]);
while(h + 1 < t && ufrac(Q[t - 1],i) * (x[Q[t - 1]] - x[Q[t - 2]]) <= ufrac(Q[t - 2],Q[t - 1]) * (x[i] - x[Q[t - 1]])) t--;
Q[t++] = i;
}
printf("%d\n",dp[n]);
}
return 0;