自动搬运

查看原文

来自洛谷，原作者为

	csyakuoi 不到普及三等的水平，超越国际金牌的野心。

搬运于2025-08-24 21:53:48，当前版本为作者最后更新于2018-10-13 11:58:54，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

使用动态规划算法解决本题。

因为单位时间内购买苦工的数量没有限制，所以我们设$dp1[i]$表示单位时间内花费$i$资源购买苦工能取得的最大生产力，那么$dp1[i]$可以用完全背包求出。

设$dp2[i][j]$表示$i$单位时间后剩下$j$资源能拥有的最大生产力。我们可以枚举时间$i$，拥有的资源量$j$，以及在第$i$单位时间用于购买苦工的资源量。利用$dp1[i]$，我们可以$O(1)$进行转移$($从下往上递推$)$，当拥有的资源数到达或超过$T$时，输出答案。

$AC$代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int n,m,t;
int kga[100],kgb[100];
int dp1[1000],dp2[1000][1000];

int main(void)
{
	scanf("%d%d%d",&n,&m,&t);
	if(m>=t){
		printf("0\n");
		return 0;
	}
	for(int i=0;i<n;i++)
		scanf("%d%d",&kga[i],&kgb[i]);
	memset(dp1,-1,sizeof(dp1));	dp1[0]=0;
	for(int i=0;i<n;i++)
		for(int j=1;j<1000;j++)
			if(j>=kga[i]&&dp1[j-kga[i]]!=-1)
				dp1[j]=max(dp1[j],dp1[j-kga[i]]+kgb[i]);
	//		完全背包计算dp1数组
    
    //		-1表示无法到达状态
	memset(dp2,-1,sizeof(dp2));	dp2[0][m]=0;
	for(int i=0;i<=1000;i++){
		if(dp2[i][t]!=-1){
			printf("%d\n",i);
			return 0;
		}//		到达t资源
		for(int j=0;j<=t;j++){
			if(dp2[i][j]==-1)
				continue;
			for(int k=0;k<=j;k++){
            	
            	//拥有j资源，花费k资源买苦工
                //则下一时刻拥有j-k+dp1[k]+dp2[i][j]资源
                
				if(dp1[k]==-1)
					continue;
				if(j-k+dp1[k]+dp2[i][j]>=t){
					printf("%d\n",i+1);
					return 0;
				}//		到达t资源
				if(dp2[i+1][j-k+dp1[k]+dp2[i][j]]<dp2[i][j]+dp1[k])
					dp2[i+1][j-k+dp1[k]+dp2[i][j]]=dp2[i][j]+dp1[k];
			}//		转移
		}
	}
	return 0;
}