打印文章
时间限制：9000/3000 MS（Java / Others）内存限制：131072/65536 K（Java / Others）总共提交：14521已接受提交：4531
有一天，零想要打印一个有N个单词的文章，而每个单词我有一个打印费用Ci。另外，零知道在一行中打印k个字将花费
M是常数。
现在，零想要知道最低成本，以完美安排文章。
5 5 五 9 五 7 五
230
Xnozero
斜率优化dp
我们以这道题为例
我们由题很容易写出dp方程，设f[i]为打印前i个位置的最小代价，则f[i] = min{f[j] + (sum[i] - sum[j])^2} + M
这样做是O(n^2)的复杂度
这个时候就需要斜率优化了
我们设k < j < i，若j比k优，则由状态转移方程有
f[j] + (sum[i] - sum[j])^2 < f[k] + (sum[i] - sum[k])^2
整理一下就是((f[j] + sum[j]^2) - (f[k] + sum[k]^2)) / (2 * sum[j] - 2 * sum[k]) < sum[i]
我们令y1 = f[j] + sum[j]^2 ,y2 = f[k] + sum[k]^2,x1 =2 * sum[j] ,x2 = 2 * sum[k]
那么就可以写成(y1 - y2)/(x1 - x2) < sum[i]
也就是说当j,k代表的两个点的斜率满足这个不等式时，j恒比k优
有什么用呢？
我们设k < j <p，且K(p,j) < K(j,k)，
那么若K(p,j) < sum[i]，则p比j优
若K(p,j) >= sum[i]，由于K(j,k) > K(p,j) > sum[i]，则j不比k优，就是说k比j优
即j一定没有贡献
这样子我们只需维护点间的斜率单调【这题是递增】，对于每个f[i]，我们只需找到最大的K<sum[i]，那么该斜率对应直线的右端点就是我们要找的最优的转移
怎么找最大的K呢？
由于我们维护的是斜率单调，即K递增，我们可以二分
特殊的，本题参照物sum是单调递增的，也就是说满足小于sum[i - 1]的一定满足小于sum[i]，用一个单调队列维护就好了
于是我们得到了本题的解
一般地，对于状态转移方程dp[i] = dp[j] + f(i,j)，若能转换成上述与斜率有关的不等式，都可以用斜率优化，O(n^2)转O(n)，是不是很神奇？
另外，若dp[i] = dp[j] + f(i)，也就是说我们只需找最优的dp[j]与当前点无关，就可以用单调队列优化
附上本题代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long int
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define fo(i,x,y) for (int i = (x); i <= (y); i++)
#define Redge(u) for (int k = head[u]; k != -1; k = edge[k].next)
using namespace std;
const int maxn = 500005,maxm = 100005,INF = 1000000000;
inline int read(){
int out = 0,flag = 1;char c = getchar();
while (c < 48 || c > 57) {if (c == '-') flag = -1; c = getchar();}
while (c >= 48 && c <= 57) {out = out * 10 + c - 48; c = getchar();}
return out * flag;
}
int n,M,sum[maxn],q[maxn],f[maxn],head = 0,tail = 0;
int getu(int u,int v){return (f[u] + sum[u] * sum[u]) - (f[v] + sum[v] * sum[v]);}
int getd(int u,int v){return 2 * (sum[u] - sum[v]);}
int getf(int i,int j){return f[j] + (sum[i] - sum[j]) * (sum[i] - sum[j]) + M;}
int main()
{
while (~scanf("%d%d",&n,&M)){
head = tail = 0;
REP(i,n) sum[i] = sum[i - 1] + read();
q[tail++] = 0;
for (int i = 1; i <= n; i++){
while (head + 1 < tail && getu(q[head + 1],q[head]) <= sum[i] * getd(q[head + 1],q[head]))
head++;
f[i] = getf(i,q[head]);
while (head + 1 < tail && getu(i,q[tail - 1]) * getd(q[tail - 1],q[tail - 2]) <= getu(q[tail - 1],q[tail - 2]) * getd(i,q[tail - 1]))
tail--;
q[tail++] = i;
}
printf("%d
",f[n]);
}
return 0;
}