自动搬运

查看原文

来自洛谷，原作者为

	ghy21 呐，马上要放晴了哦

搬运于2025-08-24 21:30:28，当前版本为作者最后更新于2019-03-27 11:00:28，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

萌新第一次写题解，望包含

题面传送门

这道题很有难度

先观察题目:不难想到是一个背包题，背包容量:m,物品重量:1,物品数量:n

物品价值是什么?

是前i个人完成软件1后,最多能完成几个软件2

这便将问题转化为完全背包了

但是,如果纯打完全背包,只能得60分

怎么优化呢?

经过观察发现:答案具有单调性

于是可以用二分答案优化了

你懂了吗?可以看代码

/*
  This code is made by ghy.
  Algorithm : Two Points Answer && Dynamic Programming (DP).
  I don't know what this code is.
*/
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int n,m,a[105],b[105],dp[105][105],l=1,r=20000;//r(max)=m(max)*day(max)=20000
bool check(int ntime){
    int time_else;
    memset(dp,0,sizeof(dp));	//记得初始化
    dp[0][0]=1;
    for(int i=1;i<=n;i++)	//枚举第i个人 
    	for(int j=0;j<=m;j++)
   			for(int k=j;k>=0;k--){
        		time_else=ntime-a[i]*(j-k);    //表示前i个人模块1做了j-k个情况下,他们能用来做模块2的时间
				if(time_else<0) 	//用ntime的时间做不了j-k个模块1		
					break;
        		if(dp[i-1][k]>0) 	//前i-1个人可以做k个模块1的同时做1个及以上的模块2
					dp[i][j]=max(dp[i][j],dp[i-1][k]+time_else/b[i]);    //状态转移方程(类完全背包) 
    		}
    return dp[n][m]>m;    //dp[n][m]:前n个人做m个模块1的同时,在time_else内还能做多少个模块2 
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&a[i],&b[i]);
    int mid;
    while(l<=r){	//二分答案,其中l,r都能取到	 
        mid=(r+l)>>1;
        if(check(mid))
			r=mid-1;
		else
			l=mid+1;
    }
    printf("%d\n",l);
    return 0;
}