P2365 任务安排

· · 题解

P2365 任务安排

算法：dp+斜率优化

首先，动态规划的状态转移方程不难写出:

f[i]=min(f[j]+time[i]*(\sum_{k=j+1}^i{cost[k]})+S*(\sum_{k=j+1}^ncost[k]))

可写作：f[i]=min(f[i],f[j]+tim[i]*(cost[i]-cost[j])+S*(cost[N]-cost[j]));
这样的方程是O(n^2)的，足以通过此题，代码如下：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
typedef long long LL;
const int MAXN=1024*5,INF=1024*1024*1024;
int N,S,cost[MAXN],tim[MAXN]/**/,f[MAXN];
int main(){
    scanf("%d%d",&N,&S);
    for(int i=1;i<=N;i++){
        scanf("%d%d",&tim[i],&cost[i]);
        tim[i]+=tim[i-1];
        cost[i]+=cost[i-1];
    }
    for(int i=1;i<=N;i++){
        f[i]=INF;
        for(int j=0;j<i;j++){
            f[i]=min(f[i],f[j]+tim[i]*(cost[i]-cost[j])+S*(cost[N]-cost[j]));
        }
    }
    printf("%d",f[N]);
    return 0;
}

仔细观察方程，可以发现这道题可以斜率优化
设f[i]为f_i,设\sum_{k=1}^icost[i]为s_i,k<j<i。如果转移j比转移k更优，则

∴f_j-t_i*(c_i-c_j)+S*(c_n-c_j)<f_k-t_i*(c_i-c_k)+S*(c_n-c_k) ∴f_j-t_i*c_i-t_i*c_j+S*c_n-S*c_j<f_k-t_i*c_i-t_i*c_k+S*c_n-S*c_k ∴f_j-t_i*c_j-S*c_j<f_k-t_i*c_k-S*c_k ∴f_j-c_j*(t_i+S)<f_k-c_k*(t_i+S) ∴f_j-f_k<(c_j-c_k)*(t_i+S) ∵c_j>c_k$即 $c_j-c_k>0

∴\displaystyle\frac{f_j-f_k}{c_j-c_k}<t_i+S即j到k的斜率小于t_i+S

∴以c_i为横轴，f_i为纵轴建立如图所示平面直角坐标系，维护一个下凸壳

step1：淘汰子问题维护队列时，将凸壳左端斜率太小的点删除（用f=t_i+S切这个凸壳），最左端点根据上面的证明即为最优子问题

step2：用原方程转移，得到i号点的横纵坐标

step3：插入i号点，维护下凸壳（如图，在插入i时，发现i的斜率小于l，即l没前途，直接弹掉）

具体维护方法见代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
typedef long long LL;
const int MAXN=1024*5,INF=1024*1024*1024;
int N,S,cost[MAXN],tim[MAXN],f[MAXN];
int dq[MAXN],L=1,R;
int main() {
    scanf("%d%d",&N,&S);
    for(int i=1; i<=N; i++) {
        scanf("%d%d",&tim[i],&cost[i]);
        tim[i]+=tim[i-1];
        cost[i]+=cost[i-1];
    }
    dq[++R]=0;
    for(int i=1; i<=N; i++) {
        while(L<R&&(f[dq[L+1]]-f[dq[L]])<=(tim[i]+S)*(cost[dq[L+1]]-cost[dq[L]])) {
            L++;
        }
        f[i]=f[dq[L]]-cost[dq[L]]*(tim[i]+S)+tim[i]*cost[i]+S*cost[N];
        while(L<R&&(f[dq[R]]-f[dq[R-1]])*(cost[i]-cost[dq[R]])
                >=(f[i]-f[dq[R]])*(cost[dq[R]]-cost[dq[R-1]])) {
            R--;
        }
        dq[++R]=i;
    }
    printf("%d",f[N]);
    return 0;
}