P1800 software [dp+二分答案]

$mathcal{Description}$

一个软件开发公司同时要开发两个软件，并且要同时交付给用户，现在公司为了尽快完成这一任务，将每个软件划分成m个模块，由公司里的技术人员分工完成，每个技术人员完成同一软件的不同模块的所用的天数是相同的，并且是已知的，但完成不同软件的一个模块的时间是不同的，每个技术人员在同一时刻只能做一个模块，一个模块只能由一个人独立完成而不能由多人协同完成。一个技术人员在整个开发期内完成一个模块以后可以接着做任一软件的任一模块。写一个程序，求出公司最早能在什么时候交付软件

$n,m<=100$

$mathcal{Solution}$

$最初想法$

开始想到设 $F[i,j,k]$ 表示前 $i$ 个技术人员, 生产完成第一个软件 $j$ 个模块和第二个软件的 $k$ 个模块所需要的 最小时间 .
但是发现加上状态转移后时间复杂度高达 $O(N^5)$ , 于是放弃这个思路.
好蠢

$正解部分$

如果能在 $x$ 时间内完成, 则必定也能在 $y>x$ 时间内完成, 答案具有 单调性.
于是考虑二分出 $mid$ , 检查其是否合法.

将员工看成 $N$ 种物品, 软件一模块数量 $M$ 看成背包容量,
相当于 $N$ 种物品去装满这个大小为 $M$ 的背包, 且背包为 完全背包.

$实现部分$

则设 $F[i,j]$ 表示前 $i$ 个员工, 完成 $j$ 个软件一模块后, 最多能完成多少软件二模块,

先二分出 $mid=L+R >> 1$ ,
$L=0,R=2*M.$

枚举 $i∈[1,N], j∈[1,i], k∈[1,j]$ ,
$i$ 员工解决 “软件一” $k$ 个模块, 还剩余 $left = mid - D_1[i]*k$ 的时间,
转移: $F[i,j] = max(lfloorfrac{left}{D_2[i]} floor+F[i-1,j-k])$

注意 $left < 0$ 或者 $F[i-1,j-k]无初值$ 时无法转移,

最后检查 $F[N,M]$ 是否大于等于 $M$ 即可.

$mathcal{Code}$

#include<bits/stdc++.h>
#define reg register

const int maxn = 105;

int N;
int M;
int Ans;

int D1[maxn];
int D2[maxn];
int F[maxn][maxn];

bool chk(int mid){
        memset(F, -1, sizeof F); F[0][0] = 0;
        for(reg int i = 1; i <= N; i ++)
                for(reg int j = 0; j <= M; j ++)
                        for(reg int k = 0; k <= j; k ++){
                                int left = mid - D1[i] * k;
                                if(left < 0 || F[i-1][j-k]==-1) continue ;
                                F[i][j] = std::max(left/D2[i] + F[i-1][j-k], F[i][j]);
                        }
        return F[N][M] >= M;
}

int main(){
        scanf("%d%d", &N, &M);
        for(reg int i = 1; i <= N; i ++) scanf("%d%d", &D1[i], &D2[i]);
        int l = 0, r = 10000;
        Ans = 0x3f3f3f3f;
        while(l <= r){
                int mid = l+r >> 1;
                if(chk(mid)) Ans = std::min(Ans, mid), r = mid - 1;
                else l = mid + 1;
        }
        printf("%d
", Ans);
        return 0;
}