博客
关于我
强烈建议你试试无所不能的chatGPT，快点击我
斜率优化入门学习+总结 Apio2011特别行动队&Apio2014序列分割&HZOI2008玩具装箱&ZJOI2007仓库建设&小P的牧场&防御准备&Sdoi2016征途...
阅读量：6341 次
发布时间：2019-06-22

本文共 8102 字，大约阅读时间需要 27 分钟。

斜率优化：

额...这是篇7个题的题解...

首先说说斜率优化是个啥，额...

f[i]=min(f[j]+xxxx(i,j)) ;   1<=j<i （O(n^2)暴力）这样一个式子，首先，如果xxxx（xxx）与j无关，那么这是一个单调队列（可以理解？）

那么我们思考一下，如果xxxx（xxx）与i,j同时相关，如何将其变成类似于单调队列的形式，从而O（n）求解

针对每一个同时有关i,j的变量，我们不妨将j的部分看做j，xx（j）和0,xx（i）对应的直线的斜率，针对而完全与i相关的变量可以无视，计算中加上或减去即可（就是单调队列），而完全与j相关的变量则可以看做是是对应直线在j点的纵坐标，即：xx（j）

那么，问题转化为了已知i-1个直线的斜率以及其上某一点的坐标，求所有直线的最大截距

那么我们思考如何用单调队列维护这一信息：我们通常用队尾的弹出操作维护的斜率单调不下降或单调不上升，因此我们可以用j这个点更新i需要满足Y（j）+K（j）*（和i相关的变量）最大，并且如果在第i个点不满足，那么第i+1的点一定也不满足（点的横坐标单调不下降或单调不上升）因此，我们可以推出单调队列弹出的条件，即：B(i,h)<B(i,h+1)或者B(i,h)>B(i,h+1)，这样就可以用单调队列维护相关信息，O(n)处理求解。

下面是七道题的题解：（代码不是很难写，但是稍微丑了点）

（1）Apio2011 特别行动队 （斜率优化入门题）

DP方程暴力的很好想，f[i]表示前i个人组成特别行动队的最大战斗力和，那么f[i]=a*(sum[i]-sum[j])^2+b*(sum[i]-sum[j])+c+f[j]

化简整理：f[i]-a*sum[i]^2-b*sum[i]=-2*a*sum[j]*sum[i]+f[j]+a*sum[j]*sum[j]-b*sum[j]+c

因此我们可以发现，Y(i,j)=f[i]-a*sum[i]^2-b*sum[i]，K(j)=-2*a*sum[j]，B(j)=f[j]+a*sum[j]*sum[j]-b*sum[j]+c

那么我们可以通过斜率优化完成，K(j)单调递减，x(i)单调递增，这样维护队尾信息的时候，如果(t-1,B(t-1))与(i,B(i))构成直线的斜率大于(t,B(t))与(i,B(i))构成直线的斜率，弹出t。

附上代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            using namespace std;#define N 1000005#define ll long long#define K(x) (-2ll*a*sum[x])#define B(x) (f[x]+a*sum[x]*sum[x]-b*sum[x])#define Y(x,y) (K(y)*sum[x]+B(y))ll f[N],sum[N],a,b,c;int q[N],n;bool cmp(int i,int j,int k){ ll x=(K(i)-K(k))*(B(j)-B(i)); ll y=(K(i)-K(j))*(B(k)-B(i)); return x>=y;}int main(){ scanf("%d",&n); scanf("%lld%lld%lld",&a,&b,&c); for(int i=1;i<=n;i++) { int x; scanf("%d",&x); sum[i]=sum[i-1]+x; } int h=0,t=0; for(int i=1;i<=n;i++) { while(h

（2）HNOI2008 玩具装箱 （斜率优化入门题）

n^2DP方程还是很好想的，f[i]表示前i个玩具装箱的最小费用为多少

转移：f[i]=min{f[j]+(sum[i]-sum[j]+i-j-L)^2};（sum[i]为c[i]的前缀和）

那么，为了简化一下方程，我们令a[i]=c[i]+1,sum[i]变为a[i]的前缀和，从而得到：

f[i]=min{f[j]+(sum[i]-sum[j]-(L+1))^2};之后另L++，得到，f[i]=min{f[j]+(sum[i]-sum[j]-L)^2};

展开，整理得到

f[i]-sum[i]^2+2*L*sum[i]=-2*sum[i]*sum[j]+f[j]+sum[j]^2+L^2+2*sum[j]*L;

从而，我们令K(j)=-2*sum[j],B(j)=f[j]+sum[j]^2+L^2+2*sum[j]*L,Y(i,j)=f[i]-sum[i]^2+2*L*sum[i];

那么，K(j)单调递减，sum[i]单调递增，那么维护队尾信息时，如果(t-1,B(t-1))与(i,B(i))构成直线的斜率大于(t,B(t))与(i,B(i))构成直线的斜率，弹出t。维护队首信息时，如果Y(h)>Y(h+1)那么弹出。

附上代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            using namespace std;#define N 50005#define ll long long#define K(x) (-2ll*sum[x])#define B(x) (f[x]+sum[x]*sum[x]+2*L*sum[x]+L*L)#define Y(x,y) (K(y)*sum[x]+B(y))ll f[N],sum[N],L;int q[N],n;bool cmp(int i,int j,int k){ ll x=(K(i)-K(k))*(B(j)-B(i)); ll y=(K(i)-K(j))*(B(k)-B(i)); return x>=y;}int main(){ scanf("%d%lld",&n,&L);L++; for(int i=1;i<=n;i++) { int x; scanf("%d",&x);x++; sum[i]=sum[i-1]+x; } int h=0,t=0; for(int i=1;i<=n;i++) { while(h
            
             Y(i,q[h+1]))h++; f[i]=Y(i,q[h])+sum[i]*sum[i]-2*L*sum[i]; while(h

（3）ZJOI2007 仓库建设 （斜率优化常见题）

这个DP方程需要稍微推一下，大概想想就应该能推出来。

我们考虑如何求将前n个点所有物品全部放在第n个位置的花费，我们需要维护一个sum[i]为P[i]的前缀和，sum1[i]为将前i个点的所有物品全部放在第i个位置的花费，那么，sum1[i]=sum[i-1]*(x[i]-x[i-1])+sum1[i-1];

f[i]表示在第i个位置建立仓库的最小花费，f[i]=min{f[j]+sum1[i]-sum1[j]-sum[j]*(x[i]-x[j])+c[i]};

那么我们化简整理一下，f[i]-sum1[i]-c[i]=-sum[j]*x[i]+f[j]-sum1[j]+sum[j]*x[j];

那么，我们令Y(i,j)=f[i]-sum1[i]-c[i],K(j)=-sum[j],B(j)=f[j]-sum1[j]+sum[j]*x[j];

那么，K(j)单调递减，x[i]单调递增，那么维护队尾信息时，如果(t-1,B(t-1))与(i,B(i))构成直线的斜率大于(t,B(t))与(i,B(i))构成直线的斜率，弹出t。维护队首信息时，如果Y(h)>Y(h+1)那么弹出。

附上代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            using namespace std;#define N 1000005#define ll long long#define K(x) (-sum[x])#define B(x) (f[x]+dis[x]*sum[x]-sum1[x])#define Y(x,y) ((K(y)*dis[x])+B(y))ll f[N],sum[N],dis[N],sum1[N],c[N];int q[N],n;bool cmp(int i,int j,int k){ ll x=(K(i)-K(k))*(B(j)-B(i)); ll y=(K(i)-K(j))*(B(k)-B(i)); return x>=y;}int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) { ll x; scanf("%lld%lld%lld",&dis[i],&x,&c[i]); sum[i]=sum[i-1]+x; sum1[i]=sum1[i-1]+sum[i-1]*(dis[i]-dis[i-1]); } int h=0,t=0; for(int i=1;i<=n;i++) { while(h
            
             =Y(i,q[h+1]))h++; f[i]=Y(i,q[h])+sum1[i]+c[i]; while(h

（4）小P的牧场（斜率优化常见题）

和上一题几乎一样，状态和转移基本没有变化，只是x[i]变成了i，其他的没有变化

直接附上代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            using namespace std;#define N 1000005#define ll long long#define K(x) (-sum[x])#define B(x) (f[x]+x*sum[x]-sum1[x])#define Y(x,y) ((K(y)*x)+B(y))ll f[N],sum[N],sum1[N],c[N];int q[N],n;bool cmp(int i,int j,int k){ ll x=(K(i)-K(k))*(B(j)-B(i)); ll y=(K(i)-K(j))*(B(k)-B(i)); return x>=y;}int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&c[i]); } for(int i=1;i<=n;i++) { ll x; scanf("%lld",&x); sum[i]=sum[i-1]+x; sum1[i]=sum1[i-1]+sum[i-1]; } int h=0,t=0; for(int i=1;i<=n;i++) { while(h
            
             =Y(i,q[h+1]))h++; f[i]=Y(i,q[h])+sum1[i]+c[i]; while(h

（5）防御准备（斜率优化常见题）

和上一题几乎一样，比上一题更简单一点，就是将sum[i]变成i...

没什么好说的...附上代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            using namespace std;#define N 1000005#define ll long long#define K(x) (-x)#define B(x) (f[x]+1ll*x*x-sum1[x])#define Y(x,y) ((1ll*K(y)*x)+B(y))ll f[N],sum1[N],c[N];int q[N],n;bool cmp(int i,int j,int k){ ll x=(K(i)-K(k))*(B(j)-B(i)); ll y=(K(i)-K(j))*(B(k)-B(i)); return x>=y;}int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&c[i]); } for(int i=1;i<=n;i++) { sum1[i]=sum1[i-1]+i-1; } int h=0,t=0; for(int i=1;i<=n;i++) { while(h
            
             =Y(i,q[h+1]))h++; f[i]=Y(i,q[h])+sum1[i]+c[i]; while(h

（6）Apio2014 序列分割

这个DP方程很简单，但是需要知道一件事...就是切的顺序和答案无关...

证明：（sum[i]是a[i]的前缀和）

设：在i,j(j>i)位置切割。

那么如果先切i，则：ans=sum[i]*(sum[n]-sum[i])+(sum[j]-sum[i])*(sum[n]-sum[j]) ;

展开：ans=sum[i]*sum[n]-sum[i]^2+sum[j]*sum[n]-sum[j]^2-sum[i]*sum[n]+sum[i]*sum[j];

整理：ans=-sum[i]^2+sum[j]*sum[n]-sum[i]*sum[n]+sum[i]*sum[j]-sum[j]^2;

再整理：ans=sum[j]*(sum[n]-sum[j])+sum[i]*(sum[j]-sum[i]);仔细观察发现，这就是先切j的答案。

因此，切割顺序与答案无关。

那么DP方程显而易见：f[i][k]表示前i个节点，切k次的最大价值并且，在第i个节点处切一次

转移：f[i][k]=max{f[j][k-1]+(sum[i]-sum[j])*(sum[n]-sum[i])};

但是这样不能斜率优化，我们考虑将k这一维移到外面

即：f[k][i]=max{f[k-1][j]+(sum[i]-sum[j])*(sum[n]-sum[i])};

这样可以发现，k只与k-1相关，我们可以通过滚动数组优化一维，省些空间，其实并不一定需要，但是这样看起来方便，写到这一步就可以展开优化了。

即：f[i]=max{g[j]+(sum[i]-sum[j])*(sum[n]-sum[i])};

整理：f[i]+sum[i]*sum[i]=sum[i]*sum[j]+g[j]+sum[i]*sum[n]-sum[j]*sum[n];

Y(i,j)=f[i]+sum[i]*sum[i];K(j)=sum[j];B(j)=g[j]+sum[i]*sum[n]-sum[j]*sum[n];

那么我们可以通过斜率优化完成，K(j)单调递增，x(i)单调递增，这样维护队尾信息的时候，如果(t-1,B(t-1))与(i,B(i))构成直线的斜率小于(t,B(t))与(i,B(i))构成直线的斜率，弹出t。维护队首信息时，如果Y(h)<Y(h+1)那么弹出。

附上代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            using namespace std;#define N 100005#define ll long long#define K(x) (sum[x])#define B(x) (g[x]-sum[x]*sum[x])#define Y(x,y) (K(y)*sum[x]+B(y))ll g[N],f[N],sum[N];int n,k,que[N];bool cmp(int i,int j,int k){ ll x=(K(i)-K(k))*(B(j)-B(i)); ll y=(K(i)-K(j))*(B(k)-B(i)); return x>=y;}int main(){ scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) { int x; scanf("%d",&x); sum[i]=sum[i-1]+x; } for(int i=1;i<=k;i++) { int h=0,t=0; for(int j=i;j<=n;j++) { while(h

（7）Sdoi2016 征途

方差是啥？百度百科：

接下来就是数学能力了...

orz orz fcwww 

附上代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            using namespace std;#define N 3005#define ll long long#define K(x) (-2ll*sum[x])#define B(x,z) (f[x][z]+sum[x]*sum[x]*m)#define Y(x,y,z) ((K(y)*m*sum[x])+B(y,z))ll f[N][N],sum[N];int q[N],n,m;bool cmp(int i,int j,int k,int z){ ll x=(K(i)-K(k))*(B(j,z)-B(i,z)); ll y=(K(i)-K(j))*(B(k,z)-B(i,z)); return x>=y;}int main(){ for(int i=0;i
            
             =Y(i,q[h+1],j-1))h++; f[i][j]=Y(i,q[h],j-1)+sum[i]*sum[i]*m; //printf("%d %d %lld\n",i,j,f[i][j]); while(h

　　

转载于:https://www.cnblogs.com/Winniechen/p/9027336.html

你可能感兴趣的文章
centos6.8 安装jenkins
查看>>
vue-cli3.0+node.js+axios跨域请求session不一样的问题
查看>>
C#发送DKIM签名的邮件
查看>>
python中获取字典的key列表和value列表
查看>>
Windows8中使用IE8等低版本浏览器
查看>>
[图形图像]一次光线追踪的尝试
查看>>
C# 中out，ref，params参数的使用
查看>>
玩转VIM编辑器-vim附加特性
查看>>
Ubuntu下有关Java和数据库的一些工作记录（二）
查看>>
java 线程
查看>>
MySql 时间函数
查看>>
解决php收邮件乱码问题
查看>>
linux shell中'',""和``的区别
查看>>
OceanBase数据库实践入门——手动搭建OceanBase集群
查看>>
WPF学习：3.Border & Brush
查看>>
Docker（二）：微服务教程
查看>>
关于JAVA项目报表选型过程
查看>>
javascript
查看>>
Spring_MVC
查看>>
Java统计文件夹中文件总行数
查看>>
喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！-- 愿君每日到此一游！
当前时间: 2025-01-12 01:03:11   当前IP: 3.140.185.250   联系邮箱:javaeecc@qq.com     Copyright © 2020 - 2022 baihongyu.com 京ICP备2021015314号-2
强烈建议你试试无所不能的CHAT-GPT，快点击我
强烈建议你试试无所不能的CHAT-GPT，快点击我