P3891 [GDOI2014] 采集资源

题意简述：

开始时你有数量为 \(m\) 的资源，有 \(n\) 种“苦工”可以不限次数地建造，每种苦工都有一个花费 \(a\) ，和一个效率 \(b\) ，要求最小化资源数量到达 \(t\) 的时间

Solution：

我们考虑先对于每一种花费 \(i\) 最大化它的“单位时间内产生的资源的数量”，记为 \(w_i\) 这可以用完全背包解决。

然后我们记状态 \(f[d][k]\) 为在第 \(d\) 天时,拥有 \(k\) 的资源时的最大效率，然后我们就可以对于每一个状态 \((d,k)\) 去枚举花费 \(j\) 然后维护第 \(d+1\) 天的 \(f\) 数组。状态转移方程为：

\(f[d+1][k-j+w[j]+f[d][k]]=\max(f[d+1][k-j+w[j]+f[d][k]],f[d][k]+w[j])\)

然后判断结束的标志就是要么 \(f[d][t]\) 合法，要么是在转移时 \(f[d+1][k-j+w[j]+f[d][k]]\) 合法且 \(k-j+w[j]+f[d][k]\ge t\)

时间复杂度 \(O(ans*t^2)\) 而且跑不满。

Code:

#include<bits/stdc++.h>
const int N=105;
const int M=1005;
int w[M],f[N][M];
using namespace std;
int n,m,t;
inline void init()
{
    for(int i=0;i<N;i++)for(int j=0;j<M;j++)f[i][j]=-1;
}
inline void Max(int &x,int y)
{
    x = x>y ? x : y;
}
inline int Min(int x,int y)
{
    return x<y ? x : y;
}
void work()
{
    cin>>n>>m>>t;
    if(m>=t){cout<<0;return ;}
    for(int i=1,x,y;i<=n;i++)
    {
        scanf("%d%d",&x,&y);
        x=Min(x,1000);
        y=Min(y,1000);
        for(int j=x;j<=t;j++)
        {
            Max(w[j],w[j-x]+y);
        }
    }
    int d=0;
    init();
    f[0][m]=0;
    while(d<=1000)
    {
        if(~f[d][t]){cout<<d;return;}
        for(int k=0;k<=t;k++)if(~f[d][k])
        for(int j=0;j<=k;j++)
        {
            if(k-j+w[j]+f[d][k]>=t){cout<<d+1;return;}
            Max(f[d+1][k-j+w[j]+f[d][k]],f[d][k]+w[j]);
        }
        d++;
    }
}
int main()
{
    //freopen("P3891.in","r",stdin);
    //freopen("P3891.out","w",stdout);
    work();
    return 0;
}