#创作计划# 浅谈斜率优化 dp
2025-07-29 14:08:08
发布于：浙江
137阅读
0回复
0点赞
正文
先看例题理解。
任务安排
dp
设 表示前 个物品被分批后的最小总费用，同时处理开机时间 对后面状态的影响，则有转移 ，显然可以预处理出来前缀和求解，变为：。
时间复杂度 。
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INT_MAX (1e18)
const int N=5e3+10;
int n,s;
int a[N],b[N],dp[N];
inline int read(){
int t=0,f=1;
register char c=getchar();
while (c<48||c>57) f=(c=='-')?(-1):(f),c=getchar();
while (c>=48&&c<=57)t=(t<<1)+(t<<3)+(c^48),c=getchar();
return f*t;
}
void solution(){
/*
*/
}
signed main(){
n=read(),s=read();
for(int i=1;i<=n;i++) a[i]=read(),b[i]=read();
for(int i=1;i<=n;i++) a[i]+=a[i-1],b[i]+=b[i-1];
for(int i=1;i<=n;i++){
int minn=INT_MAX;
for(int j=0;j<i;j++)
minn=min(minn,dp[j]+a[i]*(b[i]-b[j])+s*(b[n]-b[j]));
dp[i]=minn;
cout<<dp[i]<<" ";
}
cout<<dp[n]<<"\n";
return 0;
}
dp
将原先的式子变形：
考虑对于 ，什么时候 不优于 。
发现这个东西很像斜率表达式，那不妨设 ，则原式要求即为 与 之间直线的斜率大于等于 。
接下来看一张图：
设 斜率分别为 ， 为 。首先有 ，然后根据我们刚才的证明，有若 ，则 点优于 点，反之亦然；若 ，则 点优于 点，反之亦然。
则现在有三种情况：
- ，则 不优于 点。
- ，则 不优于 点。
- ，则 既不优于 也不优于 。
综上，上述情况下， 一定会被踢出决策候选点，所以最后是一个下凸包的结构。
现在只剩下两个关键问题：如何维护下凸包和对于每个 如何找到答案。
维护凸壳可以使用单调队列维护，队列中始终保持一个凸包的形状，那么每加入一个，只需找到相邻的两个点，并判断他们的斜率关系即可，注意要一直弹出队头（尾），知道剩下的图形是一个凸包。因为每新加入一个点，可能需要删除多个点才可以变为一个凸包。
那么对于每个 如何找到答案呢？考虑之前证明出第 个点与第 个点连线的斜率大于等于 时，第 个点更优，又因为凸壳斜率单增，所以只需要二分找到第一个大于等于 的点即可。
时间复杂度 。
dp
发现凸包单增， 单增，则维护指针记录即可。
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INT_MAX (1e18)
const int N=3e5+10;
int n,s,head,tail;
int a[N],b[N],id[N],dp[N];
inline int read(){
int t=0,f=1;
register char c=getchar();
while (c<48||c>57) f=(c=='-')?(-1):(f),c=getchar();
while (c>=48&&c<=57)t=(t<<1)+(t<<3)+(c^48),c=getchar();
return f*t;
}
void solution(){
/*
*/
}
double calc(int x,int y){
double xx=(double)(dp[y]-dp[x])/(double)(b[y]-b[x]);
return xx;
}
bool judge(int x,int y,int z){
if(calc(x,y)>calc(y,z)) return true;
return false;
}
void update(int x,int y){
dp[y]=a[y]*b[y]+s*b[n]+dp[x]-s*b[x]-a[y]*b[x];
}
signed main(){
n=read(),s=read(),head=1,tail=1;
for(int i=1;i<=n;i++)
a[i]=read(),b[i]=read();
for(int i=1;i<=n;i++) a[i]+=a[i-1];
for(int i=1;i<=n;i++) b[i]+=b[i-1];
int pos=1;
for(int i=1;i<=n;i++){
while(pos<tail&&calc(id[pos],id[pos+1])<s+a[i]) pos++;
update(id[pos],i);
while(tail>head&&judge(id[tail-1],id[tail],i)){
if(tail==pos) pos--;
tail--;
}
id[++tail]=i;
// cout<<dp[i]<<" ";
}
cout<<dp[n]<<"\n";
return 0;
}
加强版
此时发现 并不具备单调性，那么此时直接二分即可。
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INT_MAX (1e18)
const int N=3e5+10;
int n,s,head,tail;
int a[N],b[N],id[N],dp[N];
inline int read(){
int t=0,f=1;
register char c=getchar();
while (c<48||c>57) f=(c=='-')?(-1):(f),c=getchar();
while (c>=48&&c<=57)t=(t<<1)+(t<<3)+(c^48),c=getchar();
return f*t;
}
void solution(){
/*
*/
}
bool judge(int x,int y,int z){
if((dp[y]-dp[x])*(b[z]-b[y])>=(dp[z]-dp[y])*(b[y]-b[x])) return true;
return false;
}
void update(int x,int y){
dp[y]=a[y]*b[y]+s*b[n]+dp[x]-s*b[x]-a[y]*b[x];
}
bool check(int x,int y,int z){
return ((dp[y]-dp[x])>(z*(b[y]-b[x])));
}
int er(int x){
int l=1,r=tail-1,mid;
while(l<r){
mid=(l+r>>1);
if(check(id[mid],id[mid+1],x)) r=mid;
else l=mid+1;
}
if(check(id[l],id[l+1],x)) return id[l];
return id[l+1];
}
signed main(){
n=read(),s=read(),head=1,tail=1;
for(int i=1;i<=n;i++)
a[i]=read(),b[i]=read();
for(int i=1;i<=n;i++) a[i]+=a[i-1];
for(int i=1;i<=n;i++) b[i]+=b[i-1];
for(int i=1;i<=n;i++){
update(er(s+a[i]),i);
while(tail>1&&judge(id[tail-1],id[tail],i)) tail--;
id[++tail]=i;
}
cout<<dp[n]<<"\n";
return 0;
}
全部评论 8
这里的 是每次询问的 ，而我们凸包上的点其斜率一定是单增的，当 即询问单增时，我们可以使用指针简单维护；当其不单调时，我们也可以在凸包上二分来求出该点
2025-07-30 来自 浙江
0
有帮助，赞一个