Luogu P3891 采集资源

Hawking_llfz · 2019-08-26 14:36:39 · 个人记录

题目传送门

解析

Code

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define LL long long
using namespace std;
int n,m,t,a[105],b[105],f1[1005],f2[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]);
    if(m>=t)
    {
        printf("0\n");
        return 0;
    }
    memset(f1,-1,sizeof(f1));
    f1[0]=0;
    for(int i=1;i<=n;i++)
      for(int j=a[i];j<=1000;j++)
        if(f1[j-a[i]]!=-1) f1[j]=max(f1[j],f1[j-a[i]]+b[i]);
    memset(f2,-1,sizeof(f2));
    f2[0][m]=0;
    for(int i=0;i<=1000;i++)
      for(int j=0;j<=t;j++)
        if(f2[i][j]!=-1)
          for(int k=0;k<=j;k++)
            if(f1[k]!=-1)
            {
                if(j-k+f1[k]+f2[i][j]>=t)
                {
                    printf("%d\n",i+1);
                    return 0;
                }
                f2[i+1][j-k+f1[k]+f2[i][j]]=max(f2[i+1][j-k+f1[k]+f2[i][j]],f1[k]+f2[i][j]);
            }
    return 0;
}