题解 P3891 【[GDOI2014]采集资源】
csyakuoi
·
·
题解
使用动态规划算法解决本题。
因为单位时间内购买苦工的数量没有限制，所以我们设dp1[i]表示单位时间内花费i资源购买苦工能取得的最大生产力，那么dp1[i]可以用完全背包求出。
设dp2[i][j]表示i单位时间后剩下j资源能拥有的最大生产力。我们可以枚举时间i，拥有的资源量j，以及在第i单位时间用于购买苦工的资源量。利用dp1[i]，我们可以O(1)进行转移(从下往上递推)，当拥有的资源数到达或超过T时，输出答案。
```cpp
#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;
}
```