洛谷题目传送门
这是一道很难简单的动态规划题
思路：
我们可以这么想因为单位时间内购买苦工的数量没有限制，所以我们把dp[i]设成单位时间内花费i资源购买苦工能取得的最大劳动力，所以dp[i]可以用完全背包求出,因为苦工可以重复买。
我们再设dpa[i][j]表示i单位时间后剩下j有资源能拥有的最大劳动力。
我们可以依次枚举时间i，拥有的劳动力j，以及在第i单位时间用于购买苦工的劳动力。
最后利用 dp[i]进行转移，当拥有的资源数到达或超过T时输出即可。
代码：
#include<bits/stdc++.h>
using namespace std;
int n,m,t,a[105],b[105],dp[1005],dpa[1005][1005];
int main(){scanf("%d%d%d",&n,&m,&t);for(int i=1;i<=n;i++){scanf("%d%d",&a[i],&b[i]);}memset(dp,-1,sizeof(dp));memset(dpa,-1,sizeof(dpa));dp[0]=0;for(int i=1;i<=n;i++){for(int j=a[i];j<1000;j++){if(dp[j-a[i]]!=-1)dp[j]=max(dp[j],dp[j-a[i]]+b[i]);}}dpa[0][m]=0;for(int i=0;i<=1000;i++){if(dpa[i][t]!=-1){printf("%d",i);return 0;}for(int j=0;j<=t;j++){if(dpa[i][j]==-1)continue;for(int l=0;l<=j;l++){if(dp[l]==-1)continue;if(j-l+dp[l]+dpa[i][j]>=t){printf("%d",i+1);return 0;}dpa[i+1][j-l+dp[l]+dpa[i][j]]=max(dpa[i+1][j-l+dp[l]+dpa[i][j]],dpa[i][j]+dp[l]);}}}return 0;
}
题解比较垃圾,欢迎开喷