【题意】：要打印一篇文章包含n个单词，每个单词打印需要一定的代价Ci。把连续k个单词打印在同一行需要花费(∑Ci)^2 + M，问打印完整篇文章最少代价是多少。
【题解】：一个分组问题，dp解决。
设dp[i]表示把前i个单词打印完的最少代价。
dp[i] = min(dp[j] + (sum[i] - sum[j]) ^ 2 + M),1 <= j <= i - 1.
朴素dp是O(n*n)，而n<=500000，显然需要优化。
这题满足决策的单调性，所以只需要用一个单调队列维护一个下凸线，这样可以把转移降为O(1)。
【代码】：
1 #include "iostream"
2 #include "cstdio"
3 #include "cstring"
4 #include "algorithm"
5 #include "vector"
6 #include "queue"
7 #include "cmath"
8 #include "string"
9 #include "cctype"
10 #include "map"
11 using namespace std;
12 #define pb push_back
13 #define lc(x) (x << 1)
14 #define rc(x) (x << 1 | 1)
15 #define lowbit(x) (x & (-x))
16 #define ll long long
17 #define maxn 500050
18 int n, m;
19 int loc[maxn], head, tail;
20 ll sum[maxn], dp[maxn], cmp[maxn];
21 int main() {
22 while(~scanf("%d%d", &n, &m)) {
23 head = tail = 0, sum[0] = 0, dp[0] = 0;
24 loc[tail++] = 0;
25 for(int i = 1; i <= n; i++) {
26 scanf("%lld", &sum[i]);
27 sum[i] += sum[i-1];
28 }
29 for(int i = 1; i <= n; i++) {
30 while(head + 1 < tail && (cmp[loc[head+1]] - cmp[loc[head]]) <= 2 * sum[i] * (sum[loc[head+1]] - sum[loc[head]])) head++;
31 int j = loc[head];
32 dp[i] = dp[j] + (sum[i] - sum[j]) * (sum[i] - sum[j]) + m;
33 cmp[i] = dp[i] + sum[i] * sum[i];
34 while(head + 1 < tail && (cmp[loc[tail-1]] - cmp[loc[tail-2]]) * (sum[i] - sum[loc[tail-1]]) >= (cmp[i] - cmp[loc[tail-1]]) * (sum[loc[tail-1]] - sum[loc[tail-2]])) tail--;
35 loc[tail++] = i;
36 }
37 printf("%lld\n", dp[n]);
38 }
39 return 0;
40 }
41