动态规划--斜率优化

《动态规划--斜率优化》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、动态规划优化_斜率优化先来看一道题(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(j

2、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无关,右边只

3、与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(j

4、,k]>slope[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永远不会成为某个点的最优决策.现在我们有了这两个结论,怎样来优化呢?我们可以将决策放到一个队列中,利用以上两个结论剔除无用决策点,达到快速转移的目的.记队列的头指针为

5、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.还可以有不同的写法)顺便说一句,这样维护以后,队列中的"点"形成一个上凸包(联想上面说的斜率).程序大致过程fori=1tondobegin当队列不

6、为空时,更新队头;取当前队头更新f[i];用i去更新队尾;将i加入队尾.end;可以看到外层循环是O(N)的,内层里每个元素进出队列仅一次,所以总效率为O(N).code:(HDU3507)constoo=1e100;maxn=500001;vars,f:Array[0..maxn]ofint64;q:array[0..maxn]oflongint;n,m,i,h,t,c:longint;functionslope(j,k:longint):extended;beginifs[j]=s[k]thenbeginiff[j]>=f[k]thenslope:=-ooelseslope:=oo;exi

7、t;end;slope:=(f[j]-f[k]+s[j]*s[j]-s[k]*s[k])/(s[j]-s[k]);end;beginwhilenotseekeofdobeginreadln(n,m);fori:=1tondobeginreadln(c);s[i]:=s[i-1]+c;end;h:=0;t:=0;fori:=1tondobeginwhile(h