先分析出来dp的过程，然后再看能不能用斜率优化
优化的两种方式：
1.任务安排1
假如启动一次则得加上s*(sumc[n]-sumc[i-1])即可
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=5e3+10; int n,s; int a[N],c[N],t[N]; ll f[N]; int main() { scanf("%d%d",&n,&s); for(int i=1;i<=n;i++) { scanf("%d%d",&t[i],&c[i]); t[i]+=t[i-1],c[i]+=c[i-1];//求ci和ti的前缀和 f[i]=1e18;//因为求最小值初始化为正无穷 } f[0]=0;//前0个任务处理完的方案为0 for(int i=1;i<=n;i++)//枚举每个位置 for(int j=0;j<i;j++)//枚举可以用来更新的位置 f[i]=min(f[i],f[j]+(ll)t[i]*(c[i]-c[j])+(ll)s*(c[n]-c[j]));//状态计算 printf("%lld\n",f[n]); return 0; }
2.任务安排2
题目跟第一题一模一样就是数据范围变大了，所以得用斜率优化
我们可以将状态转移方程变一下性，因为i这个点是由j这个点转移过来的，所以自变量是j，因变量是f[j]，那么我们可以将式子做等价变形得到：
然后看第j这个点的截距假如使得截距最小则f[i]最小，第i这个点的斜率是固定为（sumTi+S），则我们可以将直线进行平移，直到碰到的第一个点就是b的最小
因为0~i这里面的点并不都一定对未来产生影响，所以这里用到单调队列里的思想，把永远不会作为最小值的点即使弹出，只要有一个点在某两个点的上方则永远都不会用来更新最小值，把不用的点全部删掉就是凸包（所有的点都在另一侧）的下边界，所以我们只需要维护凸包的下边界即可
找使得i的最的点，就是在凸包中找到第一个斜率大于k的点
怎么在维护的凸包中找到截距最小的点？
相当于在一个单调队列里找到第一个大于某个数的点
1.二分查找这个数
2.分析推理。这题的特列：因为斜率是单调递增的，新加的点的横坐标也是单调递增的
所以维护好的凸包，使得第i这个位置最小就是q【hh】
对应的两个删除操作需要满足的情况：
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=3e5+10; int n,s; ll t[N],c[N]; ll f[N]; int q[N]; int main() { scanf("%d%d",&n,&s); for(int i=1;i<=n;i++) { scanf("%lld%lld",&t[i],&c[i]); t[i]+=t[i-1];//求t的前缀和 c[i]+=c[i-1];//求c的前缀和 } int hh=0,tt=0; q[0]=0;//刚开始队列里有一个元素0，因为0也可以用来更新，表示前0个选的合法方案 for(int i=1;i<=n;i++) { while(hh<tt&&(f[q[hh+1]]-f[q[hh]])<= (t[i]+s)*(c[q[hh+1]]-c[q[hh]])) hh++;//把不满足条件的队头删掉 int j=q[hh];//使得i最小就是hh了 f[i]=f[j]-(t[i]+s)*c[j]+t[i]*c[i]+s*c[n];//更新状态 while(hh<tt&&(f[q[tt]]-f[q[tt-1]])*(c[i]-c[q[tt]])>= (f[i]-f[q[tt]])*(c[q[tt]]-c[q[tt-1]])) tt--;//把不满足的队尾删掉 q[++tt]=i;//把当前点加进队列中来 } printf("%lld\n",f[n]);//删除前n个的处理完的合法方案的最小值 return 0; }
3.任务安排3
这题跟较上一题就数据的变化，因为ti可能是负数，使得斜率（sumTi+s）不在是单调的了，就不能用单调队列来做了，但是可以用二分来做，因为凸包里的数还是递增的
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=3e5+10; int n,s; ll t[N],c[N]; ll f[N]; int q[N]; int main() { scanf("%d%d",&n,&s); for(int i=1;i<=n;i++) { scanf("%lld%lld",&t[i],&c[i]); t[i]+=t[i-1];//求t的前缀和 c[i]+=c[i-1];//求c的前缀和 } int hh=0,tt=0; q[0]=0;//刚开始队列里有一个元素0，因为0也可以用来更新，表示前0个选的合法方案 for(int i=1;i<=n;i++) { int l=hh,r=tt; while(l<r)//二分查找队列中的第一个大于等于k的点j { int mid=l+r>>1; if((f[q[mid+1]]-f[q[mid]])>(t[i]+s)*(c[q[mid+1]]-c[q[mid]])) r=mid;//假如斜率比当前k的大，则缩小范围 else l=mid+1; } int j=q[l]; f[i]=f[j]-(t[i]+s)*c[j]+t[i]*c[i]+(ll)s*c[n];//更新状态 while(hh<tt&&(__int128_t)(f[q[tt]]-f[q[tt-1]])*(c[i]-c[q[tt]])>= (__int128_t)(f[i]-f[q[tt]])*(c[q[tt]]-c[q[tt-1]])) tt--;//把不满足的队尾删掉,这里longlong会爆，所以改成double或者__int128_t也行 q[++tt]=i;//把当前点加进队列中来 } printf("%lld\n",f[n]);//删除前n个的处理完的合法方案的最小值 return 0; }
4.运输小猫
题意：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是递增的所以可以用单调队列来做也即第一个情况的优化，用二分来做也行
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+10,P=110; int n,m,p; ll d[N],t[N],a[N],s[N]; ll f[P][N]; int q[N]; ll get_y(int k,int j)//状态计算中的因变量也就是y { return f[j-1][k]+s[k]; } int main() { scanf("%d%d%d",&n,&m,&p); for(int i=2;i<=n;i++) { scanf("%lld",&d[i]); d[i]+=d[i-1];//求距离前缀和 } for(int i=1;i<=m;i++) { int h; scanf("%d%lld",&h,&t[i]); a[i]=t[i]-d[h];//求ai } sort(a+1,a+m+1);//将ai进行排序 for(int i=1;i<=m;i++) s[i]=s[i-1]+a[i];//求ai的前缀和 memset(f,0x3f,sizeof f); for(int i=0;i<=p;i++) f[i][0]=0;//i位饲养员领走0只小猫的方案是0 for(int j=1;j<=p;j++)//枚举饲养员的个数 { int hh=0,tt=0;//初始化单调队列 q[0]=0; for(int i=1;i<=m;i++)//枚举m只小猫 { while(hh<tt&&(get_y(q[hh+1],j)-get_y(q[hh],j))<= a[i]*(q[hh+1]-q[hh])) hh++;//把前面小于等于当前斜率的数筛掉 int k=q[hh];//使得i最小就是队头的元素q[hh] f[j][i]=f[j-1][k]-a[i]*k+s[k]+a[i]*i-s[i];//状态更新 while(hh<tt&&(get_y(q[tt],j)-get_y(q[tt-1],j))*(i-q[tt])>= (get_y(i,j)-get_y(q[tt],j))*(q[tt]-q[tt-1])) tt--;//把结尾斜率太小的筛掉 q[++tt]=i;//把当前点加入队列中 } } printf("%lld\n",f[p][m]);//输出结果 return 0; }
滚动数组优化
因为更新第i层只用到了i-1也就是上一层的状态，所以把上一层状态存下来即可，在用来更新第i层
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+10,P=110; int n,m,p; ll d[N],t[N],a[N],s[N]; ll f[N],g[N]; int q[N]; ll get_y(int k,int j)//状态计算中的因变量也就是y { return g[k]+s[k];//用上一层状态更新 } int main() { scanf("%d%d%d",&n,&m,&p); for(int i=2;i<=n;i++) { scanf("%lld",&d[i]); d[i]+=d[i-1];//求距离前缀和 } for(int i=1;i<=m;i++) { int h; scanf("%d%lld",&h,&t[i]); a[i]=t[i]-d[h];//求ai } sort(a+1,a+m+1);//将ai进行排序 for(int i=1;i<=m;i++) s[i]=s[i-1]+a[i];//求ai的前缀和 memset(f,0x3f,sizeof f); f[0]=g[0]=0;//i位饲养员领走0只小猫的方案是0 for(int j=1;j<=p;j++)//枚举饲养员的个数 { int hh=0,tt=0;//初始化单调队列 q[0]=0; memcpy(g,f,sizeof f);//把上一层状态更新过来 for(int i=1;i<=m;i++)//枚举m只小猫 { while(hh<tt&&(get_y(q[hh+1],j)-get_y(q[hh],j))<= a[i]*(q[hh+1]-q[hh])) hh++;//把前面小于等于当前斜率的数筛掉 int k=q[hh];//使得i最小就是队头的元素q[hh] f[i]=g[k]-a[i]*k+s[k]+a[i]*i-s[i];//状态更新 while(hh<tt&&(get_y(q[tt],j)-get_y(q[tt-1],j))*(i-q[tt])>= (get_y(i,j)-get_y(q[tt],j))*(q[tt]-q[tt-1])) tt--;//把结尾斜率太小的筛掉 q[++tt]=i;//把当前点加入队列中 } } printf("%lld\n",f[m]);//输出结果 return 0; }
