• 斜率优化DP

    先分析出来dp的过程，然后再看能不能用斜率优化 

    优化的两种方式：

    目录

    1.任务安排1

    2.任务安排2

    3.任务安排3

    4.运输小猫

    1.任务安排1

    300. 任务安排1 - AcWing题库

    假如启动一次则得加上s*(sumc[n]-sumc[i-1])即可

    1. #include
    2. using namespace std;
    3. typedef long long ll;
    4. const int N=5e3+10;
    5. int n,s;
    6. int a[N],c[N],t[N];
    7. ll f[N];
    8. int main()
    9. {
    10.     scanf("%d%d",&n,&s);
    11.     for(int i=1;i<=n;i++)
    12.     {
    13.         scanf("%d%d",&t[i],&c[i]);
    14.         t[i]+=t[i-1],c[i]+=c[i-1];//求ci和ti的前缀和
    15.         f[i]=1e18;//因为求最小值初始化为正无穷
    16.     }
    17.     f[0]=0;//前0个任务处理完的方案为0
    18.     for(int i=1;i<=n;i++)//枚举每个位置
    19.         for(int j=0;j//枚举可以用来更新的位置
    20.               f[i]=min(f[i],f[j]+(ll)t[i]*(c[i]-c[j])+(ll)s*(c[n]-c[j]));//状态计算
    21.     printf("%lld\n",f[n]);
    22. 	return 0;
    23. }

    2.任务安排2

    301. 任务安排2 - AcWing题库

    题目跟第一题一模一样就是数据范围变大了，所以得用斜率优化

    我们可以将状态转移方程变一下性，因为i这个点是由j这个点转移过来的，所以自变量是j，因变量是f[j]，那么我们可以将式子做等价变形得到：

    然后看第j这个点的截距假如使得截距最小则f[i]最小，第i这个点的斜率是固定为（sumTi+S），则我们可以将直线进行平移，直到碰到的第一个点就是b的最小

     因为0~i这里面的点并不都一定对未来产生影响，所以这里用到单调队列里的思想，把永远不会作为最小值的点即使弹出，只要有一个点在某两个点的上方则永远都不会用来更新最小值，把不用的点全部删掉就是凸包（所有的点都在另一侧）的下边界，所以我们只需要维护凸包的下边界即可

     

     找使得i的最的点，就是在凸包中找到第一个斜率大于k的点

     怎么在维护的凸包中找到截距最小的点？

    相当于在一个单调队列里找到第一个大于某个数的点

    1.二分查找这个数

    2.分析推理。这题的特列：因为斜率是单调递增的，新加的点的横坐标也是单调递增的

    所以维护好的凸包，使得第i这个位置最小就是q【hh】

     对应的两个删除操作需要满足的情况：

    1. #include
    2. using namespace std;
    3. typedef long long ll;
    4. const int N=3e5+10;
    5. int n,s;
    6. ll t[N],c[N];
    7. ll f[N];
    8. int q[N];
    9. int main()
    10. {
    11.     scanf("%d%d",&n,&s);
    12.     for(int i=1;i<=n;i++)
    13.     {
    14.         scanf("%lld%lld",&t[i],&c[i]);
    15.         t[i]+=t[i-1];//求t的前缀和
    16.         c[i]+=c[i-1];//求c的前缀和
    17.     }
    18.     int hh=0,tt=0;
    19.     q[0]=0;//刚开始队列里有一个元素0，因为0也可以用来更新，表示前0个选的合法方案
    20.     for(int i=1;i<=n;i++)
    21.     {
    22.         while(hh1]]-f[q[hh]])<=
    23.               (t[i]+s)*(c[q[hh+1]]-c[q[hh]])) hh++;//把不满足条件的队头删掉
    24.         int j=q[hh];//使得i最小就是hh了
    25.         f[i]=f[j]-(t[i]+s)*c[j]+t[i]*c[i]+s*c[n];//更新状态
    26.         while(hh-1]])*(c[i]-c[q[tt]])>=
    27.               (f[i]-f[q[tt]])*(c[q[tt]]-c[q[tt-1]])) tt--;//把不满足的队尾删掉
    28.         q[++tt]=i;//把当前点加进队列中来
    29.     }
    30.     printf("%lld\n",f[n]);//删除前n个的处理完的合法方案的最小值
    31.     return 0;
    32. }

    3.任务安排3

    302. 任务安排3 - AcWing题库

    这题跟较上一题就数据的变化，因为ti可能是负数，使得斜率（sumTi+s）不在是单调的了，就不能用单调队列来做了，但是可以用二分来做，因为凸包里的数还是递增的

     

    1. #include
    2. using namespace std;
    3. typedef long long ll;
    4. const int N=3e5+10;
    5. int n,s;
    6. ll t[N],c[N];
    7. ll f[N];
    8. int q[N];
    9. int main()
    10. {
    11.     scanf("%d%d",&n,&s);
    12.     for(int i=1;i<=n;i++)
    13.     {
    14.         scanf("%lld%lld",&t[i],&c[i]);
    15.         t[i]+=t[i-1];//求t的前缀和
    16.         c[i]+=c[i-1];//求c的前缀和
    17.     }
    18.     int hh=0,tt=0;
    19.     q[0]=0;//刚开始队列里有一个元素0，因为0也可以用来更新，表示前0个选的合法方案
    20.     for(int i=1;i<=n;i++)
    21.     {
    22.         int l=hh,r=tt;
    23.         while(l//二分查找队列中的第一个大于等于k的点j
    24.         {
    25.             int mid=l+r>>1;
    26.             if((f[q[mid+1]]-f[q[mid]])>(t[i]+s)*(c[q[mid+1]]-c[q[mid]])) r=mid;//假如斜率比当前k的大，则缩小范围
    27.             else l=mid+1;
    28.         }
    29.         int j=q[l];
    30.         f[i]=f[j]-(t[i]+s)*c[j]+t[i]*c[i]+(ll)s*c[n];//更新状态
    31.         while(hh__int128_t)(f[q[tt]]-f[q[tt-1]])*(c[i]-c[q[tt]])>=
    32.               (__int128_t)(f[i]-f[q[tt]])*(c[q[tt]]-c[q[tt-1]])) tt--;//把不满足的队尾删掉,这里longlong会爆，所以改成double或者__int128_t也行
    33.         q[++tt]=i;//把当前点加进队列中来
    34.     }
    35.     printf("%lld\n",f[n]);//删除前n个的处理完的合法方案的最小值
    36.     return 0;
    37. }

    4.运输小猫

    303. 运输小猫 - AcWing题库

    题意：p个饲养员从一号山走到终点，把已经玩完的猫接走，问所有猫总共等待时间的总和的最小值是多少

    di:从1到i的距离   ti小猫玩耍的时间   si是饲养员开始的时间   si+▲t+di-ti是小猫等待的时间

    Ai=ti-di是饲养员最早出发的时间

     然后我们按照Ai进行从小到大排序

    每次每个饲养员可以接走一段小猫，然后这段小猫总共的等待时间就是最后一个的Ai与前面所有数的差值，加上接走【l,r】则总共等待时间为（l-r+1）*Ar-(sum(r)-sum(l-1))

    然后问我们如何划分取到最小值

    小知识（越靠近内层循环的定义到数组的后面去，因为内存的缓存机制，连续的内存时间会快），

    因为这题第二层循环的是i所以i在f数组的第二维

    S是ai的前缀和，k是由第k个更新过来 ，因为这里的ai是递增的所以可以用单调队列来做也即第一个情况的优化，用二分来做也行

    1. #include
    2. using namespace std;
    3. typedef long long ll;
    4. const int N=1e5+10,P=110;
    5. int n,m,p;
    6. ll d[N],t[N],a[N],s[N];
    7. ll f[P][N];
    8. int q[N];
    9. ll get_y(int k,int j)//状态计算中的因变量也就是y
    10. {
    11.     return f[j-1][k]+s[k];
    12. }
    13. int main()
    14. {
    15.     scanf("%d%d%d",&n,&m,&p);
    16.     for(int i=2;i<=n;i++)
    17.     {
    18.         scanf("%lld",&d[i]);
    19.         d[i]+=d[i-1];//求距离前缀和
    20.     }
    21.     for(int i=1;i<=m;i++)
    22.     {
    23.         int h;
    24.         scanf("%d%lld",&h,&t[i]);
    25.         a[i]=t[i]-d[h];//求ai
    26.     }
    27.     sort(a+1,a+m+1);//将ai进行排序
    28.     for(int i=1;i<=m;i++) s[i]=s[i-1]+a[i];//求ai的前缀和
    29.     memset(f,0x3f,sizeof f);
    30.     for(int i=0;i<=p;i++) f[i][0]=0;//i位饲养员领走0只小猫的方案是0
    31.     for(int j=1;j<=p;j++)//枚举饲养员的个数
    32.     {
    33.         int hh=0,tt=0;//初始化单调队列
    34.         q[0]=0;
    35.         for(int i=1;i<=m;i++)//枚举m只小猫
    36.         {
    37.             while(hhget_y(q[hh+1],j)-get_y(q[hh],j))<=
    38.                   a[i]*(q[hh+1]-q[hh])) hh++;//把前面小于等于当前斜率的数筛掉
    39.             int k=q[hh];//使得i最小就是队头的元素q[hh]
    40.             f[j][i]=f[j-1][k]-a[i]*k+s[k]+a[i]*i-s[i];//状态更新
    41.             while(hhget_y(q[tt],j)-get_y(q[tt-1],j))*(i-q[tt])>=
    42.                   (get_y(i,j)-get_y(q[tt],j))*(q[tt]-q[tt-1])) tt--;//把结尾斜率太小的筛掉
    43.             q[++tt]=i;//把当前点加入队列中
    44.         }
    45.     }
    46.     printf("%lld\n",f[p][m]);//输出结果
    47.     return 0;
    48. }

    滚动数组优化

    因为更新第i层只用到了i-1也就是上一层的状态，所以把上一层状态存下来即可，在用来更新第i层

    1. #include
    2. using namespace std;
    3. typedef long long ll;
    4. const int N=1e5+10,P=110;
    5. int n,m,p;
    6. ll d[N],t[N],a[N],s[N];
    7. ll f[N],g[N];
    8. int q[N];
    9. ll get_y(int k,int j)//状态计算中的因变量也就是y
    10. {
    11.     return g[k]+s[k];//用上一层状态更新
    12. }
    13. int main()
    14. {
    15.     scanf("%d%d%d",&n,&m,&p);
    16.     for(int i=2;i<=n;i++)
    17.     {
    18.         scanf("%lld",&d[i]);
    19.         d[i]+=d[i-1];//求距离前缀和
    20.     }
    21.     for(int i=1;i<=m;i++)
    22.     {
    23.         int h;
    24.         scanf("%d%lld",&h,&t[i]);
    25.         a[i]=t[i]-d[h];//求ai
    26.     }
    27.     sort(a+1,a+m+1);//将ai进行排序
    28.     for(int i=1;i<=m;i++) s[i]=s[i-1]+a[i];//求ai的前缀和
    29.     memset(f,0x3f,sizeof f);
    30.     f[0]=g[0]=0;//i位饲养员领走0只小猫的方案是0
    31.     for(int j=1;j<=p;j++)//枚举饲养员的个数
    32.     {
    33.         int hh=0,tt=0;//初始化单调队列
    34.         q[0]=0;
    35.         memcpy(g,f,sizeof f);//把上一层状态更新过来
    36.         for(int i=1;i<=m;i++)//枚举m只小猫
    37.         {
    38.             while(hhget_y(q[hh+1],j)-get_y(q[hh],j))<=
    39.                   a[i]*(q[hh+1]-q[hh])) hh++;//把前面小于等于当前斜率的数筛掉
    40.             int k=q[hh];//使得i最小就是队头的元素q[hh]
    41.             f[i]=g[k]-a[i]*k+s[k]+a[i]*i-s[i];//状态更新
    42.             while(hhget_y(q[tt],j)-get_y(q[tt-1],j))*(i-q[tt])>=
    43.                   (get_y(i,j)-get_y(q[tt],j))*(q[tt]-q[tt-1])) tt--;//把结尾斜率太小的筛掉
    44.             q[++tt]=i;//把当前点加入队列中
    45.         }
    46.     }
    47.     printf("%lld\n",f[m]);//输出结果
    48.     return 0;
    49. }

  • 相关阅读:
    随机专享记录第一话 -- RustDesk的自我搭建和使用
    Linux中/etc下面passwd和shadow文件介绍
    《 Python List 列表全实例详解系列（九）》__列表反转（6种方法）
    ElasticSearch+MongoDB：搜索-关键字联想
    如何在VScode和Jetbrain上使用备受争议的GitHub Copilot
    2022年牛客多校第四场补题
    springboot毕设项目高校宿舍管理系统的设计与实现ukgdt（java+VUE+Mybatis+Maven+Mysql）
    MYSQL函数，一篇文章看完！
    我的PFC岩土颗粒流离散元分析攻略（附赠学习资料）
    数据集成：数据挖掘的准备工作之一
  • 原文地址：https://blog.csdn.net/m0_63729880/article/details/127697927