任务分配——斜率优化dp——运输小猫

任务分配

思路：fi：分配前i个任务的最小花费
状态转移：考虑前一批的选择方法
f[i] = f[j] -s*c[j]-t[i]c[j]+sc[n]+t[i]c[i];
当数据增大的时候：
双重循环可能会超时，所以需要优化：
考虑转移方程
f[i] = f[j] -sc[j]-t[i]c[j]+sc[n]+t[i]c[i];
阔以得到：
f[j] = sc[j]+t[i]c[j]+f[i]-sc[n]+t[i]*c[i];
可以看作是cj为自变量，fj为因变量的函数，当斜率变化的时候从以前的点中求最小的截距；
考虑优化斜率，凸包的优化方式：
查询凸包：若队头的两个点的斜率小于当前斜率，就删除队头，找到大的为止，然后插入。
维护凸包：
因为fi 和 ci 的值都在增大，所以新的点可能会把后面的点从凸包的边上删掉，具体方法为：
比较最后两个点的斜率，倒数第二个点和新点的斜率 如果前者大，就删除队尾元素，直到新点的斜率是最大的为止。然后插入新点。

当斜率不再单调递增的时候，查找的时候使用二分

代码：

#include 
#include 
using namespace std;
const int N = 3e5+10;
int n,s;
long long t[N],c[N];
long long f[N];
int q[N];
int main() {
    cin>>n>>s;
    for(int i = 1;i<=n;i++){
        long long tt,cc;
        scanf("%lld%lld", &tt,&cc);
        t[i] = t[i-1]+tt;
        c[i] = c[i-1]+cc;
    }
    int hh = 0,tt = 0;
    q[0] = 0;//没有一个点的时候
    for(int i  = 1;i<=n;i++){
        while(hh<tt&&((f[q[hh+1]]-f[q[hh]])<=(s+t[i])*(c[q[hh+1]]-c[q[hh]]))) hh++;
        int j = q[hh];
        f[i] = f[j] -s*c[j]-t[i]*c[j]+s*c[n]+t[i]*c[i];
        while(hh<tt&&((f[q[tt]]-f[q[tt-1]])*(c[i]-c[q[tt-1]])>=(f[i]-f[q[tt-1]])*(c[q[tt]]-c[q[tt-1]]))) tt--;
        q[++tt] = i;
    }
    cout<<f[n];
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

二分写法:

#include 
#include 
using namespace std;
const int N = 3e5+10;
int n,s;
long long t[N],c[N];
long long f[N];
int q[N];
int main() {
    cin>>n>>s;
    for(int i = 1;i<=n;i++){
        long long tt,cc;
        scanf("%lld%lld", &tt,&cc);
        t[i] = t[i-1]+tt;
        c[i] = c[i-1]+cc;
    }
    int hh = 0,tt = 0;
    q[0] = 0;//没有一个点的时候
    for(int i  = 1;i<=n;i++){
        int l = hh,r = tt;
        while(l<r){
            int mid = (l+r)>>1;
            if((f[q[mid+1]]-f[q[mid]])>(s+t[i])*(c[q[mid+1]]-c[q[mid]])) r = mid;
            else l = mid +1;
        }
        
        int j = q[r];
        f[i] = f[j]-s*c[j]-t[i]*c[j]+s*c[n]+t[i]*c[i];
        while(hh<tt&&((double)(f[q[tt]]-f[q[tt-1]])*(c[i]-c[q[tt-1]])>=(double)(f[i]-f[q[tt-1]])*(c[q[tt]]-c[q[tt-1]]))) tt--;
        q[++tt] = i;
    }
    cout<<f[n];
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

运输小猫

斜率优化dp的应用
代码：

#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int N = 1e5+10,M = 1e5+10,P = 110;
LL a[N];
LL f[P][N],s[N];
LL d[N];
int q[N];
int n,m,p;
LL get_y(int j,int k){
    return f[j-1][k]+s[k];
}
int main() {
    cin>>n>>m>>p;
    for(int i = 2;i<=n;i++){
        scanf("%d",&d[i]);
        d[i] +=d[i-1];
    }

    for(int i=1;i<=m;i++){
        int h,t;
        scanf("%d%d",&h,&t);
        a[i] = t-d[h];
    }

    sort(a+1,a+1+m);
    for(int i = 1;i<=m;i++) s[i] = s[i-1]+a[i];

    memset(f,0x3f,sizeof f);
    for(int i = 0;i<=p;i++) f[i][0] = 0;

    for(int j = 1;j<=p;j++){
        int hh = 0,tt = 0;
        for(int i = 1;i<=m;i++){
            while(hh<tt&&(get_y(j,q[hh+1])- get_y(j,q[hh]))<=a[i]*(q[hh+1]-q[hh])) hh++;
            int k = q[hh];
            f[j][i] = get_y(j,k)+a[i]*i-a[i]*k-s[i];
            while(hh<tt&&((get_y(j,q[tt])- get_y(j,q[tt-1]))*(i-q[tt])>=(get_y(j,i)-get_y(j,q[tt]))*(q[tt]-q[tt-1]))) tt--;
            q[++tt] = i; 
        }
    }

    cout<<f[p][m];
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48