斜率优化dp专题

斜率优化dp专题HDU3507,BZOJ101015973437109619113675能用斜率优化的dp题一般都需要证明决策单调性（然而我到现在还没有搞懂到底何为决策单调）。一般有几种思路：1)将得到的数据打表，一般打表打[L,R]内这一段的值，判断是否基本满足四边形不等式：的模样，或者还有敲暴力之后看看dp数组内的值是否单调。2)在敲暴力的过程中能感觉到，需要从前面已经得到的结果查找最优解，但是这个最优解在一定范围内，而不必全部找过来的时候，就可能需要用上优化了。3)重要的是如果能写出《1D1D》中的经典模型的形式：f(x)=minx−1i=1{f(i)+w[i,x]}那几乎就可以确定出题人就在考斜率优化dp。一旦确定这题可以用斜率优化dp做，那么题目就变成了板子题。按我最近刷这类题目的方法来看，其实只要拆分成下面几步就可以做：1)对题目进行单调性分析并且列出转移方程式。由于最近刷的题目早就知道是斜率优化所以没有分析单调性，而单调性的得出还是需要转移方程式辅助。由于O(n)的平摊复杂度需要用到单调队列deque，我们需要针对缩进front指针和rear指针的两个while操作进行设计函数：（就以上面提及的标准函数为例）2)为了使队列中的deq[L]弹出，就需要deq[L]不比dep[L+1]优：设i,j,k满足条件j<k<i，且i从j转移比从k转移优，则可以列出等式：通过对该式子分离出带有i的变量，可以得到一个解题最重要的不等式（斜率优化的代码辣么短都是因为这个不等式的关系）。如果提取不出上述要求的不等式就不能用斜率优化dp解题。最后就能精简出一个函数g(x,y)满足g(x,y)<=w[i]。但是我并不建议实际代码写成g(x,y)。3)为了使队列中的deq[R]弹出，就需要deq[R]对于deq[R−1]和i都不优：设a,b,c满足条件a<b<c<i，如果满足：则deq[R]不优。因为当g(deq[R−1],deq[R])<=w[i]时，deq[R−1]更优；当g(deq[R−1],deq[R])>w[i]时，g(dep[R],i)>w[i]，i更优。所以一个斜率优化的dp的重点在于g(x,y)的推导（不是很喜直线方程的写法）以及两个缩进while语句的符号问题（反正只要考虑左侧的要求能够传递到右侧而不会改变即可）。斜率优化dp应用举例：斜率优化dp应用举例BZOJ1010HNOI2008玩具装箱toyBZOJ1597USACO2008土地并购HDU3507PrintArticleBZOJ3437小P的牧场BZOJ1096ZJOI2007仓库建设BZOJ1911Apoi2010特别行动队BZOJ3675Apio2014序列分割BZOJ1010HNOI2008玩具装箱toyDescriptionP教授要去看奥运，但是他舍不下他的玩具，于是他决定把所有的玩具运到北京。他使用自己的压缩器进行压缩，其可以将任意物品变成一堆，再放到一种特殊的一维容器中。P教授有编号为1…N的N件玩具，第i件玩具经过压缩后变成一维长度为Ci。为了方便整理，P教授要求在一个一维容器中的玩具编号是连续的。同时如果一个一维容器中有多个玩具，那么两件玩具之间要加入一个单位长度的填充物。形式地说如果将第i件玩具到第j个玩具放到一个容器中，那么容器的长度将为x=j−i+∑jk=iCk。制作容器的费用与容器的长度有关，根据教授研究，如果容器长度为x，其制作费用为(x−L)2，其中L是一个常量。P教授不关心容器的数目，他可以制作出任意长度的容器，甚至超过L。但他希望费用最小。我们可以得到满足样例的结果是分成{1},{2},{3,4},{5}四组，并且我们也可以发现这个表格是满足四边形不等式的。首先考虑采用O(logn)的单调栈完成这个题目。我们考虑当前的dp(i)能够去更新哪些点，那么能够更新的点就会形成一段区间。我们在栈中存储的值是每个不同的dp(i)所能更新的区间左端点，而右端点则是接下来的一个左端点（栈顶的右端点是n），可更新的最优区间就是[stk[i],str[i+1])。查找结果的时候，我们只需要用二分查找找到包含该位置的最优区间；更新最优解的时候，始终考虑以该点作为更新点，可以更新到的离n的最远点在哪里。如果比当前的区间还优（即用当前区间的更新点不比用dp[i]优），将其覆盖；否则只会优于当前区间的部分区间，满足01性，同样通过二分查找可以找到结果。平摊的复杂度最大就是O(logn)。我写O(nlogn)的时候反而比O(n)卡了更久，没有搞明白区间和更新点之间的关系，但是搞明白之后对单调性有更清楚的认识。#include<cstdio>#include<cstring>#include<algorithm>usingnamespacestd;#defineM50005intn,Len,stk[M],pre[M],top=0;longlongsum[M],dp[M];longlongsqr(longlongx){returnx*x;}longlongcalc(intL,intR){returndp[L]+sqr(R-L-1+sum[R]-sum[L]-Len);}intmain(){scanf("%d%d",&n,&Len);for(inti=1,x;i<=n;i++){scanf("%d",&x);sum[i]=sum[i-1]+x;}/*for(inti=0;i<n;i++){for(intj=i+1;j<=n;j++)printf("[%d,%d]%lld",i,j,calc(i,j));puts("");}//打印出w[i,j]，观察答案与单调性*/dp[0]=0;stk[++top]=0;pre[top]=0;for(inti=1;i<=n;i++){intL=1,R=top,res=0;while(L<=R){intmid=L+R>>1;if(stk[mid]<=i){res=mid;L=mid+1;}elseR=mid-1;}dp[i]=calc(pre[res],i)while(top&&i<stk[top]&&calc(pre[top],stk[top])>calc(i,stk[top]))--top;L=stk[top],R=n,res=n+1;while(L<=R){intmid=L+R>>1;if(calc(pre[top],mid)>calc(i,mid)){res=mid;R=mid-1;}elseL=mid+1;}if(res!=n+1){//当i根本不优的时候不能插入istk[++top]=res;pre[top]=i;}}printf("%lld\n",dp[n]);}尝试推一下g(x,y)函数：此处还要注意有两种写法，一种是采用double的g(x,y)写法，一种是将分子分母分离交叉相乘的写法，但是g(x,y)写法的缺点是会出现分母为0的情况需要特判，一个不小心还会出现精度问题。从速度上来讲，用除法显然比用乘法慢（在BZOJ上亲测用g(x,y)慢了50+ms）。/*g(x,y)写法*/#defineM50005intn,Len;longlongdp[M],sum[M];longlongsqr(longlongx){returnx*x;}doubleg(intx,inty){return(dp[y]+sqr(sum[y]+y+Len+1)-dp[x]-sqr(sum[x]+x+Len+1))/(2.0*(sum[y]-sum[x]+y-x));}intdeq[M],L=0,R=-1;intmain(){scanf("%d%d",&n,&Len);for(inti=1,x;i<=n;i++){scanf("%d",&x);sum[i]=sum[i-1]+x;}deq[++R]=0;for(inti=1;i<=n;i++){while(L<R&&g(deq[L],deq[L+1])<=sum[i]+i)++L;dp[i]=dp[deq[L]]+sqr(sum[i]-sum[deq[L]]+i-deq[L]-1-Len);while(L<R&&g(deq[R-1],deq[R])>g(deq[R],i))--R;deq[++R]=i;}printf("%lld\n",dp[n]);return0;}/*分离分子分母的写法*/#defineM50005intn,Len;intdeq[M],L=0,R=-1;longlongdp[M],sum[M];longlongsqr(longlongx){returnx*x;}longlongup(intx,inty){returndp[y]-dp[x]+sqr(sum[y]+y+Len+1)-sqr(sum[x]+x+Len+1);}longlongdown(intx,inty){return2*(sum[y]-sum[x]+y-x);}intmain(){scanf("%d%d",&n,&Len);for(inti=1,x;i<=n;i++){scanf("%d",&x);sum[i]=sum[i-1]+x;}deq[++R]=0;for(inti=1;i<=n;i++){while(L<R&&up(deq[L],deq[L+1])<=(sum[i]+i)*down(deq[L],deq[L+1]))++L;dp[i]=dp[deq[L]]+sqr(sum[i]-sum[deq[L]]+i-deq[L]-1-Len);while(L<R&&up(deq[R-1],deq[R])*down(deq[R],i)>up(deq[R],i)*down(deq[R-1],deq[R]))--R;deq[++R]=i;}printf("%lld\n",dp[n]);return0;}BZOJ1597USACO2008土地并购DescriptionKano准备扩大他的农场，眼下必须购买N块长方形土地。如果Kano买一块土地，价格就是土地的面积。他也可以选择并购一块土地，并购的价格为这些土地中最大的长乘以最大的宽，比如Kano购买3x5和5x3的土地，只需要支付5x5=25元，比分开买合算。请你帮他计算购买所有土地的最小费用。SampleInput&Output4100115152051100500啊啊，先膜一下“水”大犇。题目描述只是因为我把这题搬到自家oi上的。在写本题的O(n^2)暴力dp的时候有没有想过常数优化？毕竟那些长宽小于某一块土地的都对答案没啥贡献，可以算是附赠的。而且如果在一维有序的情况下只需要理论下限的O(n)复杂度就可以过掉了。那么此题的转移就很显然了：将两者都倒序枚举，除去干扰单调性的数据，则长单调递减，宽单调递增。可以得到转移方程：structnode{inth,w;booloperator<(constnode&cmp)const{if(h!=cmp.h)returnh>cmp.h;returnw>cmp.w;}}Base[M],Q[M];intqtop=0;intdeq[M],L=0,R=-1;longlongdp[M];longlongup(intx,inty){returndp[y]-dp[x];}longlongdown(intx,inty){returnQ[x+1].h-Q[y+1].h;}intmain(){intn;scanf("%d",&n);for(inti=1;i<=n;i++)scanf("%d%d",&Base[i].h,&Base[i].w);sort(Base+1,Base+n+1);intw=0;for(inti=1;i<=n;i++){if(Base[i].w<=w)continue;Q[++qtop]=Base[i];w=Base[i].w;}n=qtop;deq[++R]=0;for(inti=1;i<=n;i++){while(L<R&&up(deq[L],deq[L+1])<Q[i].w*down(deq[L],deq[L+1]))++L;dp[i]=dp[deq[L]]+1LL*Q[deq[L]+1].h*Q[i].w;while(L<R&&up(deq[R-1],deq[R])*down(deq[R],i)>up(deq[R],i)*down(deq[R-1],deq[R]))--R;deq[++R]=i;}printf("%lld\n",dp[n]);return0;}HDU3507PrintArticleDescriptionKano想要打印一篇含有N个单词的文章，每个单词的打印费用是Ci，一行打印k个单词的费用是：#include<cstdio>#include<cstring>#include<algorithm>#defineM500005usingnamespacestd;intsum[M],dp[M],deq[M];intsqr(intx){returnx*x;}intup(intx,inty){return(sqr(sum[y])-sqr(sum[x])+dp[y]-dp[x]);}intdown(intx,inty){return2*(sum[y]-sum[x]);}intmain(){intn,Mt;while(scanf("%d%d",&n,&Mt)==2){for(inti=1,x;i<=n;i++){scanf("%d",&x);sum[i]=sum[i-1]+x;}intL=0,R=-1;deq[++R]=0;for(inti=1;i<=n;i++){while(L<R&&up(deq[L],deq[L+1])<=sum[i]*down(deq[L],deq[L+1]))++L;dp[i]=dp[deq[L]]+sqr(sum[i]-sum[deq[L]])+Mt;while(L<R&&up(deq[R-1],deq[R])*down(deq[R],i)>=up(deq[R],i)*down(deq[R-1],deq[R]))--R;deq[++R]=i;}printf("%d\n",dp[n]);}return0;}BZOJ3437小P的牧场Description小P在MC里有n个牧场，自西向东呈一字形排列（用1…n编号），于是他就烦恼了：为了控制这n个牧场，他需要在某些牧场上面建立控制站。每个牧场上只能建立一个控制站，每个控制站控制的牧场是它所在的牧场一直到它西边第一个控制站的所有牧场（它西边第一个控制站所在的牧场不被控制；如果它西边不存在控制站，那么它控制西边所有的牧场）。每个牧场被控制都需要一定的花费，而且该花费等于它到控制它的控制站之间的牧场数目（不包括自身，但包括控制站所在牧场）乘上该牧场的放养量，在第i个牧场建立控制站的花费是ai，每个牧场i的放养量是bi，理所当然，小P需要总花费最小，但是小P的智商有点不够用了，所以这个最小总花费就由你来算出啦。SampleInput&Output4242431429这个题目稍微不水的地方莫非是如何用连续和求出第i个控制站控制前面牧场的所用费用？hwzer大犇说正推比较烦。个人不怎么觉得……我们先看一下w[i,j]=∑jk=i{B[k]∗(j−k)}=∑jk=i{B[k]∗j−B[k]∗k}，前半部分采用正常的前缀和相减再乘以j得到，而后半部分维护一个相同模样的前缀和即可。方程：#include<cstdio>#include<cstring>#include<algorithm>usingnamespacestd;#defineM1000005intA[M],B[M];longlongsum1[M],sum2[M],dp[M];intdeq[M],L=0,R=-1,n;longlongcalc(intL,intR){returndp[L]+A[R]+(sum1[R]-sum1[L])*R-(sum2[R]-sum2[L]);}longlongup(intL,intR){returndp[R]-dp[L]+sum2[R]-sum2[L];}longlongdown(intL,intR){returnsum1[R]-sum1[L];}intmain(){scanf("%d",&n);for(inti=1;i<=n;i++)scanf("%d",&A[i]);for(intj=1;j<=n;j++)scanf("%d",&B[j]);for(intj=1;j<=n;j++){sum1[j]=sum1[j-1]+B[j];sum2[j]=sum2[j-1]+1LL*B[j]*j;}deq[++R]=0;for(inti=1;i<=n;i++){while(L<R&&up(deq[L],deq[L+1])<i*down(deq[L],deq[L+1]))++L;dp[i]=calc(q[L],i);while(L<R&&up(deq[R-1],deq[R])*down(deq[R],i)>=down(deq[R-1],deq[R])*up(deq[R],i))--R;deq[++R]=i;}printf("%lld\n",dp[n]);return0;}BZOJ1096ZJOI2007仓库建设DescriptionL公司有N个工厂，由高到底分布在一座山上,工厂1在山顶，工厂N在山脚。由于这座山处于高原内陆地区（干燥少雨），L公司一般把产品直接堆放在露天，以节省费用。突然有一天，L公司的总裁L先生接到气象部门的电话，被告知三天之后将有一场暴雨，于是L先生决定紧急在某些工厂建立一些仓库以免产品被淋坏。由于地形的不同，在不同工厂建立仓库的费用可能是不同的。第i个工厂目前已有成品Pi件，在第i个工厂位置建立仓库的费用是Ci。对于没有建立仓库的工厂，其产品应被运往其他的仓库进行储藏，而由于L公司产品的对外销售处设置在山脚的工厂N，故产品只能往山下运（即只能运往编号更大的工厂的仓库），当然运送产品也是需要费用的，假设一件产品运送1个单位距离的费用是1。假设建立的仓库容量都都是足够大的，可以容下所有的产品。在每一行，你都将得到以下数据：1.工厂i距离工厂1的距离Xi（其中X1=0）2.工厂i目前已有成品数量Pi3.在工厂i建立仓库的费用Ci请你帮助L公司寻找一个仓库建设的方案，使得总的费用（建造费用+运输费用）最小。SampleInput&Output3051053100961032同上，水题（直接复制的，改下就A了）。#include<cstdio>#include<cstring>#include<algorithm>usingnamespacestd;#defineM1000005intX[M],A[M],B[M];longlongsum1[M],sum2[M],dp[M];intdeq[M],L=0,R=-1,n;longlongcalc(intL,intR){returndp[L]+A[R]+(sum1[R]-sum1[L])*X[R]-(sum2[R]-sum2[L]);}longlongup(intL,intR){returndp[R]-dp[L]+sum2[R]-sum2[L];}longlongdown(intL,intR){returnsum1[R]-sum1[L];}intmain(){scanf("%d",&n);for(inti=1;i<=n;i++)scanf("%d%d%d",&X[i],&B[i],&A[i]);for(intj=1;j<=n;j++){sum1[j]=sum1[j-1]+B[j];sum2[j]=sum2[j-1]+1LL*B[j]*X[j];}deq[++R]=0;for(inti=1;i<=n;i++){while(L<R&&up(deq[L],deq[L+1])<X[i]*down(deq[L],deq[L+1]))++L;dp[i]=calc(deq[L],i);while(L<R&&up(deq[R-1],deq[R])*down(deq[R],i)>=down(deq[R-1],deq[R])*up(deq[R],i))--R;deq[++R]=i;}printf("%lld\n",dp[n]);return0;}BZOJ1911Apoi2010特别行动队DescriptionSampleInput&Output4-110-2022349这里要注意的是a<0，所以如果写成g(x,y)的形式要小心。方程：#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#defineM1000005usingnamespacestd;intn,a,b,c;longlongsum[M],dp[M];longlongsqr(longlongx){returnx*x;}longlongcalc(longlongx){returna*sqr(x)+b*x+c;}longlongup(intx,inty){returndp[y]-dp[x]+a*sqr(sum[y])-a*sqr(sum[x])+b*(sum[x]-sum[y]);}longlongdown(intx,inty){return2*a*(sum[y]-sum[x]);}intdeq[M],L=0,R=-1;intmain(){scanf("%d%d%d%d",&n,&a,&b,&c);for(inti=1,x;i<=n;i++){scanf("%d",&x);sum[i]=sum[i-1]+x;}deq[++R]=0;for(inti=1;i<=n;i++){while(L<R&&up(deq[L],deq[L+1])>=sum[i]*down(deq[L],deq[L+1]))++L;dp[i]=dp[deq[L]]+calc(sum[i]-sum[deq[L]]);while(L<R&&up(deq[R-1],deq[R])*down(deq[R],i)>=up(deq[R],i)*down(deq[R-1],deq[R]))--R;deq[++R]=i;}cout<<dp[n]<<endl;}BZOJ3675Apio2014序列分割Description小H最近迷上了一个分隔序列的游戏。在这个游戏里，小H需要将一个长度为n的非负整数序列分割成k+1个非空的子序列。为了得到k+1个子序列，小H需要重复k次以下的步骤：1.小H首先选择一个长度超过1的序列（一开始小H只有一个长度为n的序列，也就是一开始得到的整个序列）；2.选择一个位置，并通过这个位置将这个序列分割成连续的两个非空的新序列。每次进行上述步骤之后，小H将会得到一定的分数。这个分数为两个新序列中元素和的乘积。小H希望选择一种最佳的分割方式，使得k轮之后，小H的总得分最大。SampleInput&Output734134023108二维的斜率优化题。这题的难点在于如何理解最后得到的分数与切的顺序无关。可以这么想：从某段序列中间切一刀，两边和相乘，看做左边的每小段区间和右边的每小段区间分别相乘。异侧的区间处理完了，接下来就要处理同侧的区间，此时就采用分治的思想，将问题划归到左区间