动态规划--斜率优化.doc

动态规划优化_斜率优化
先来看一道题(HDU3507):
题意:给出N个单词,每个单词有个非负权值Ci,将k个单词排在一行的费用为(∑Ci)^2+M.求最优方案,使得总费用最小.
我们很容易得到一个O(N^2)的算法:
s[i]表示前i个单词的权值和.
先写个东西在这:所有元素非负的数组的前缀和值随下标增加单调递增.后面会用到.
f[i]表示将前i个单词排版完毕后的最优值,f[i]=min{f[j]+(s[i]-s[j])^2+M}.
但题目中N的范围是500000.这个算法明显不行.考虑如何优化.
我们固定i,考虑它的两个一般决策点j,k(jos]+(s[i]-s[pos])^2+M,即i从pos转移的代价.
如果决策点k优于j,那么就有g[k]s[j],我们在不等式两边除以(s[k]-s[j]).
不等式化为(f[k]-f[j]+s[k]^2-s[j]^2)/(s[k]-s[j])<2*s[i].
方便起见,我们将左边分式的分子分母同时变号.
(f[j]-f[k]+s[j]^2-s[k]^2)/(s[j]-s[k])<2*s[i].
可以看到不等式左边与i无关,右边只与i有关.(而且左边像一个两点间的斜率式).
记slope[j,k]=(f[j]-f[k]+s[j]^2-s[k]^2)/(s[j]-s[k]).
好了,现在我们有一个结论.
△对于i的两个决策点j,k(js[i]>slope[j,k].
因此这里的优劣应该是全局的,而不只限于i.
我们再来考虑三个点j,k,l(jslope[k,l],我们看看能得到什么.
1.若slope[k,l]<2*s[i].那么由之前的结论(△),l比k优.
2.若slope[k,l]>2*s[i],则slope[j,k]>2*s[i],那么由之前的结论(△),决策j不比k差.
综上,如果slope[j,k]>slope[k,l],k是可以淘汰掉的.
我们又得到一个结论.
△对于三个决策点j,k,l(jslope[k,l],那么k永远不会成为某个点的最优决策.
现在我们有了这两个结论,怎样来优化呢?
我们可以将决策放到一个队列中,利用以上两个结论剔除无用决策点,达到快速转移的目的.
记队列的头指针为h,尾指针为t.
对于队列的头部,如果slope[q[h],q[h+1]]<2*s[i],那么,q[h]一定可以去掉了.h=h+1.
事实上经过这样的调整后,q[h]就是i的最有决策,直接取来更新就是了.
更新出f[i]后,将f[i]从尾部加入队列,并用i去剔除无用决策.
对于队列的尾部,如果slope[q[t-1],q[t]]>slope[q[t],i],那么q[t]可以去掉.t=t-1.
(这里我是按照我自己写程序的习惯写的,先用i去更新队尾再加入i.还可以有不同的写法)
顺便说一句,这样维护以后,队列中的"点"形成一个上凸包(联想上面说的斜率).
程序大致过程
for i=1 to n do
begin
当队列不为空时,更新队头;
取当前队头更新f[i];
用i去更新队尾;
将i加入队尾.
end;
可以看到外层循环是O(N)的,内层里每个元素进出队列仅一次,所以总效率为O(N).
code:(HDU3507)
const oo=1e100;
maxn=500001;
var s,f:Array[0..maxn] of int64;
q:array[0..maxn] of longint;
n,m,i,h,t,c:longint;
function slope(j,k:longint):extended;
begin
if s[j]=s[k] then
begin
if f[j]>=f[k] then slope:=-oo
else slope:=oo;
exit;
end;
slope:=(f[j]-f[k]+s[j]*s[j]-s[k]*s[k])/(s[j]-s[k]);
end;
begin
while not seekeof do
begin
readln(n,m);
for i:=1 to n do
begin
readln(c);
s[i]:=s[i-1]+c;
end;
h:=0; t:=0;
for i:=1 to n do
begin
while (hslope(q[t],i)) do dec(t);
inc(t); q[t]:=i;
end;
writeln(f[n]);
end;
end.

Bzoj 1010 [hnoi2008]toy
题目大意：给n个数，求将这些数切成数段，每段的长度为（sum+（i-j+1）-l）^2,求总的长度和最小。
裸dp dp[i] := min(dp[k] + (f[i]-f[j]-c) 有 ik通过枚举的j可知，所以在斜率一定的情况下，直线 k？+ans 第一个碰到的决策点即使ans最小。
然后通过斜率优化，可以证明决策点的最优，构建维护一个单调队列（点与点之间的斜率单调递增）（队尾维护），然后队首则维护首2点斜率大于k（k也可以推出随i增加单调的）
{补充：单调队列维护下凸性，队首维护解决当前最优解，队尾维护则是删除上凸点}
Dp[x] = min(dp[i]+(f[x]-f[i]-c)^2)
=f[x]^2+min(dp[i]-2f[x](f[i]+c)+(f[i]+c)^2)
设 dp[x]-f[x]^2=G dp[i]+(f[i]+c)^2 = Ti 2(f[i]+c) = Hi
原式 = G = Ti –f[x]Hi
直线 = Ti = G+f[x]Hi
斜率 = Tj-Ti / Hj-Hi
const oo=1<<60;
var f,s,q:array[0..50001] of int64;
n,l,i,j,c,h,t:longint;
function min(a,b:int64):int64;
begin
if a>b then exit(b); exit(a);
end;
function slope(j,k:longint):extended;
begin
exit((f[j]-f[k]-sqr(s[k]+k)+sqr(s[j]+j))/(s[j]+j-s[k]-k))
end;
begin
readln(n,l);
for i:=1 to n do
begin
readln(c);
s[i]:=s[i-1]+c;
end;
h:=0; t:=0;
for i:=1 to n do
begin
while (hslope(q[t],i)) do dec(t);
inc(t);
q[t]:=i;
end;
writeln(f[n]);
end.

APIO2010 特别行动队
【题目描述】
你有一支由 n 名预备役士兵组成的部队，士兵从1到n编号，要将他们拆分成若干特别行动队调入战场。出于默契的考虑，同一支特别行动队中队员的编号应该连续，即为形如(i, i + 1, …, i + k)的序列。
编号为 i 的士兵的初始战斗力为 xi ，一支特别行动队的初始战斗力 x为队内士兵初始战斗力之和，即 x = xi + xi+1 + … + xi+k。
　　通过长期的观察，你总结出一支特别行动队的初始战斗力 x将按如下经验公式修正为x'：x' = ax^2 + bx + c，其中 a, b, c是已知的系数（a < 0）。
　　作为部队统帅，现在你要为这支部队进行编队，使得所有特别行动队修正后战斗力之和最大。试求出这个最大和。
　　例如， 你有4名士兵， x1 = 2, x2 = 2, x3 = 3, x4 = 4。经验公式中的参数为 a = –1, b = 10, c = –20。此时，最佳方案是将士兵组成 3个特别行动队：第一队包含士兵1和士兵2，第二队包含士兵3，第三队包含士兵 4。特别行动队的初始战斗力分别为4, 3, 4，修正后的战斗力分别为 4, 1, 4。修正后的战斗力和为 9，没有其它方案能使修正后的战斗力和更大。
【输入文件】
输入由三行组成。第一行包含一个整数 n，表示士兵的总数。第二行包含三个整数 a, b, c，经验公式中各项的系数。第三行包含 n 个用空格分隔的整数 x1, x2, …, xn，分别表示编号为1, 2, …, n的士兵的初始战斗力。
【输出文件】
输出一个整数，表示所有特别行动队修正后战斗力之和的最大值。
【输入样例】
4
-1 10 -20
2 2 3 4
【输出样例】
9
【数据范围】
20%的数据中，n ≤ 1000；
50%的数据中，n ≤ 10,000；
100%的数据中，1 ≤ n ≤ 1,000,000，–5 ≤ a ≤ –1，|b| ≤ 10,000,000，|c| ≤
10,000,000，1 ≤ xi ≤ 100。

【题目分析】

首先看到题目就可以知道这是一道动态规划，然而朴素的n^2算法只能拿到20分。

首先，对于这个题来说，其决策是单调的，这样我们就可以用单调性把时间复杂度优化到nlogn，实践证明这样可以过7~8个点。

然后决策单调了，我们就会想到斜率……

设对于f[i]，由k决策更新比j决策更优，且k[(s*sj^2-b*sj+f[j])-(a*sk^2-b*sk+f[k])]/(sj-sk)

设g[i]=a*si^2-b*si+f[i]，那么我们就可以把si作为横坐标，g[i]作为纵坐标来表示斜率，这样就可以维护一个凸形的曲线，每次把队首斜率小于2*a*si的点出队，用队首的点计算f[i]和g[i]，再用g[i]去维护队列曲线的凸形。
program test1;
var s,f,g:array[0..1000000]of int64;
d:array[0..1000000]of longint;
t,w,i,j,n:longint;
a,b,c:int64;
function xl(i,jlongint):extended;
begin
exit((g[j]-g[i])/(s[j]-s[i]));
end;
begin
readln(n);
readln(a,b,c);
for i:=1 to n do
begin
read(s[i]);
inc(s[i],s[i-1]);
end;
t:=0;w:=0;d[0]:=0;g[0]:=0;
for i:=1 to n do
begin
while (t=2*a*s[i]) do inc(t);
j:=d[t];
f[i]:=f[j]+a*sqr(s[i]-s[j])+b*(s[i]-s[j])+c;
g[i]:=a*sqr(s[i])-b*s[i]+f[i];
while (w>t)and(xl(d[w],i)>xl(d[w-1],d[w])) do dec(w);
inc(w);
d[w]:=i;
end;
writeln(f[n]);
end.

第二种题解：
const oo=2000000000;
var
q,num:array[0..1000001] of longint;
f,s:array[0..1000001] of extended;
n,i,h,t:longint;
w,a,b,c:extended;
function slope(j,k:longint):extended;
begin
exit((f[j]-f[k]+a*s[j]*s[j]-a*s[k]*s[k]-b*s[j]+b*s[k])/(s[j]-s[k]))
end;
begin
readln(n);
readln(a,b,c);
for i:=1 to n do
begin
read(num[i]);
s[i]:=s[i-1]+num[i];
end;
h:=0; t:=0;
for i:=1 to n do
begin
while (h=2*a*s[i]) do inc(h);
w:=s[i]-s[q[h]];
f[i]:=f[q[h]]+a*w*w+b*w+c;
while (h出于默契的考虑，同一支特别行动队中队员的编号应该连续，即为形如(i, i + 1, …, i + k)的序列。编号为 i 的士兵的初始战斗力为 xi ，一支特别行动队的初始战斗力 x 为队内士兵初始战斗力之和，即 x = xi + xi+1 + … + xi+k。通过长期的观察，你总结出一支特别行动队的初始战斗力 x 将按如下经验公式修正为 x'：x' = ax2 + bx + c，其中 a, b, c 是已知的系数（a < 0）。作为部队统帅，现在你要为这支部队进行编队，使得所有特别行动队修正后战斗力之和最大。试求出这个最大和。
例如，你有 4 名士兵，x1 = 2, x2 = 2, x3 = 3, x4 = 4。经验公式中的参数为 a = –1,b = 10, c = –20。此时，最佳方案是将士兵组成 3 个特别行动队：第一队包含士兵1 和士兵 2，第二队包含士兵 3，第三队包含士兵 4。特别行动队的初始战斗力分别为 4, 3, 4，修正后的战斗力分别为 4, 1, 4。修正后的战斗力和为 9，没有其它方案能使修正后的战斗力和更大。
【输入格式】
输入由三行组成。第一行包含一个整数 n，表示士兵的总数。第二行包含三
个整数 a, b, c，经验公式中各项的系数。第三行包含 n 个用空格分隔的整数 x1,x2, …, xn，分别表示编号为 1, 2, …, n 的士兵的初始战斗力。
【输出格式】
输出一个整数，表示所有特别行动队修正后战斗力之和的最大值。
【样例输入】
4
-1 10 -20
2 2 3 4
【数据范围】
20%的数据中，n ≤ 1000；
50%的数据中，n ≤ 10,000；
【样例输出】
9
100%的数据中，1 ≤ n ≤ 1,000,000，–5 ≤ a ≤ –1，|b| ≤ 10,000,000，|c| ≤10,000,000，1 ≤ xi ≤ 100。
此题DP方程很容易想出来,f[i]为前i个士兵的最大值，f[i]:=max(f[j]+a*t^2+b*t+c)
t:=s[i]-s[j],s是前缀和但是由于时间复杂度为O(N^2),需要进行优化。
考试的时候我用的是一个小优化，但是效果很显著，过了8组，
由方程可知，函数由f[j]+h[j]组成，而h[i]又与i有关，所以不能之间单调队列，
我想的是h[j]取得最大的时候是s[j]最接近s[i]+b/(2*a)的时候，
所以当jf[k]+h[k]可得到
(f[j]-f[k]+a*(sqr(s[j])-sqr(s[k]))+b*(s[k]-s[j]))/(s[j]-s[k])<2*a*s[i]
这样我们成功地排除掉了s[i]的干扰。然后我们可以维护一个队列,
设x[j,k]=(f[j]-f[k]+a*(sqr(s[j])-sqr(s[k]))+b*(s[k]-s[j]))/(s[j]-s[k])
使队列中的2*a*s[i]>x[i,i+1]>x[i+1,i+1]>......
然后每次到i的时候维护一下队列，队首即为最优。然后在维护一下队尾，保持其单调性即可。
第一种优化：
program commando;
var
n,i,j,k,p,x:longint;
t,a,b,c,q:extended;
s:array[0..1000000] of extended; //extended在32位运算速度>int64
f:array[0..1000000] of extended;
begin
assign(input,'commando.in'); reset(input);
assign(output,'commando2.out'); rewrite(output);
read(n);
read(a,b,c);
for i:=1 to n do
begin
read(x);
s[i]:=s[i1]+x;
end;
for i:=1 to n do f[i]:=-100000000;
f[0]:=0; //初值
p:=0;
for j:=1 to n do
for k:=p to j-1 do
begin
t:=s[j]-s[k];
q:=a*t*t+b*t+c;
if f[j]close(input); close(output);
end.
第二种优化
program commando2; //单调性优化
{$inline on}
var
n,i,x,l,r:longint;
t,a,b,c,k:extended;
f,s:array[0..1000000] of extended;
dui:array[0..1000000] of longint;
function slope(j,k:longint):extended; inline;
begin slope:=(f[j]-f[k]+a*(sqr(s[j])-sqrs[k]))+b*(s[k]-s[j])){/(s[j]-s[k])};{除法变乘法更快}
end;
begin
assign(input,'commando.in'); reset(input);
assign(output,'commando.out'); rewrite(output);
read(n);
read(a,b,c);
for i:=1 to n do
begin
read(x);
s[i]:=s[i-1]+x;
end;
fillchar(f,sizeof(f),200); //要赋初值，中间点可能乘下来为负
f[0]:=0;
l:=0; r:=1; dui[1]:=0;
for i:=1 to n do
begin
t:=2*a*s[i];
while (l[dui[r]]-s[i])<=slope(dui[r],i)*(s[dui[r-1]]-s[dui[r]])) do dec(r); //不为最优的出队
inc(r); dui[r]:=i;
end;
writeln(f[n]:0:0);
close(input); close(output);
end.

锯木场选址 （CEOI2004）
[题目描述]
从山顶上到山底下沿着一条直线种植了n棵老树。当地的政府决定把他们砍下来。为了不浪费任何一棵木材，树被砍倒后要运送到锯木厂。木材只能按照一个方向运输：朝山下运。山脚下有一个锯木厂。另外两个锯木厂将新修建在山路上。你必须决定在哪里修建两个锯木厂，使得传输的费用总和最小。假定运输每公斤木材每米需要一分钱。
任务
你的任务是写一个程序：
从标准输入读入树的个数和他们的重量与位置
计算最小运输费用
将计算结果输出到标准输出
输入
输入的第一行为一个正整数n——树的个数（2≤n≤20 000）。树从山顶到山脚按照1，2……n标号。
接下来n行，每行有两个正整数（用空格分开）。
第i+1行含有：wi——第i棵树的重量（公斤为单位）和 di——第i棵树和第i+1棵树之间的距离，1≤wi ≤10 000，0≤di≤10 000。最后一个数dn，表示第n棵树到山脚的锯木厂的距离。
保证所有树运到山脚的锯木厂所需要的费用小于2000 000 000分。
输出
输出只有一行一个数：最小的运输费用。
样例输入
9
1 2
2 1
3 3
1 1
3 2
1 6
2 1
1 2
1 1
样例输出
26

Const
maxn=20001;
var f,w,d,sw,sd,c,q:array[0..maxn] of longint;
n,i,j,tmp,ans,h,t:longint;
function cost(l,r:longint):longint;
begin
cost:c[r]-c[l-1]-sw[l-1]*(sd[r]-sd[l-1]);
end;
function slope(j,k:longint):extended;
begin
slope:=(sw[k]*sd[k]-sw[j]*sd[j])/(sw[k]-sw[j]);
end;
begin
readln(n);
for i:=1 to n do readln(w[i],d[i]);
for i:=1 to n+1 do
begin
sw[i]:=sw[i-1]+w[i];
sd[i]:=sd[i-1]+d[i-1];
end;
for i:=1 to n+1 do c[i]:=c[i-1]+sw[i-1]*d[i-1];
h:=1; t:=1; q[1]:=1;
for i:=2 to n do
begin
while (h1,n+1);
while (hslope(q[t],i)) do dec(t);
inc(t);
q[t]:=i;
end;
ans:=maxlongint;
for i:=2 to n do
if ans>f[i] then ans:=f[i];
writeln(Ans);
end.

Poj1180
题目大意 ：给定n个工作，可以任意分组，最后每个工作的花费是O[i]*f[i],其中O[i]是i所在分组整体被完成的时间，给定开始时间，机器启动时间S，求完成所有任务最小花费。

算法 ：动态规划 + 斜率优化

思路 ：首先想到了dp[i] = min{dp[j] + (S + O[j] + sum[i] – sum[j]) * f[i] ) (j < i)但是这是二维的方程，需要优化成一维，但是这个式子很难化解成f[i] – f[j] = k (g[i] – g[j]) + b的形式，而且如果将j和i分在一组，O[j]的值也会改变，无法用斜率搞，最后看了网上大牛才知，设定状态

Dp[i] = min{dp[j] + (S + sumt[i] – sumt[j] ) * sumf[i] {sumt[i] =t[i] + t[i + 1]…….}, sumf[i] = f[i] + f[i + 1]….

然后化解这个式子就能斜率优化了。这里处理O[i]也算是一个技巧了，将由工作i导致的i之后的花费加到i上，这样每次的开始时间都成为了0，从后往前dp即可，其他都一样。

var f,tx,fx,st,sf,q:array[0..100001] of longint; n,s,i,h,t:longint; function slope(i,j:longint):extended; begin exit((f[i]-f[j])/(st[i]-st[j])); end;begin readln(n); readln(s); for i:=1 to n do readln(tx[i],fx[i]); for i:=n downto 1 do begin st[i]:=st[i+1]+tx[i]; sf[i]:=sf[i+1]+fx[i]; end; h:=0; t:=0; for i:=n downto 1 do begin while (hslope(q[t],i)) do dec(t); inc(t); q[t]:=i; end; writeln(f[1]);end.

poj 3709
题意是给你一个n长度递增数列，将其分组，每组不少于m个，每组的cost是每组中所有元素减去里面最小元素的值的总和，要求你算最小的cost。我想说这类的分组问题一般都是dp解决的，这题也不例外，dp状态也很好设定，dp[i]表示前i个元素的cost最小值，当然是已经分好组了，因为没限定你要分几组就是一维的状态，但是把状态方程列出来后就会发现一个问题，状态转移方程dp[i]=dp[tem]+sum[i]-sum[tem]-(i-tem)*a[tem+1];mo(n),很快啊，二维的斜率优化就是用四边形不等式。这里需要说一个细节if(!(G(x,y)*S(y,z)extended;
begin
y:=f[j]-f[k]-s[j]+s[k]+num[j+1]*j-num[k+1]*k;
x:=num[j+1]-num[k+1];
if x=0 then
if y>=0 then exit(k+m)
else exit(n+1);
slope:=y/x;
if slope readln(dnum);
for d:=1 to dnum do
begin
readln(n,m);
fillchar(s,sizeof(s),0);
fillchar(f,sizeof(f),0);
for i:=1 to n do
begin
read(num[i]);
s[i]:=s[i-1]+num[i];
end;

readln;
h:=0; t:=0;
for i:=m to n do
begin
while (h=slope(q[t],i)) do dec(t);
inc(t); q[t]:=i;
end;
writeln(f[n]:0:0);
end;
end.

Poj2018
【问题描述】
题意很简单，就是给你n个数，求一个连续数串的平均值最大，数串长度不小于F
n<=100000
【分析】
在不考虑数据范围的情况下，可以很容易地写出O(n^2)的动规方程，f[i]=max{(sum[i]-sum[j-1])/(i-j+1)}
如果我们把sum的图像画出来，那么我们发