bzoj4457: 游戏任务--双层01背包

这题和NOIP的金明的预算方案(？)很像，只不过附件的数量增多了

如果对主件进行一次01背包，再套一层附件的01背包O(n⁴)肯定会爆。。

所以我们可以先预处理出，对于每个主件，花的时间为k的情况下，最大的经验值，用01背包做

然后再对每个主件进行01背包，这样就去掉了一层循环

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define maxn 102
using namespace std;
long long n[maxn*5],v[maxn][maxn*5],c[maxn][maxn*5],t[maxn][maxn*5],f[maxn*5];
int N,T;
int main(){
    scanf("%d%d", &N, &T);
    for (int i=1; i<=N; i++){
        scanf("%lld%lld%lld", &n[i], &v[i][0], &c[i][0]);
        for (int j=1; j<=n[i]; j++)
            scanf("%lld%lld", &v[i][j], &c[i][j]);
    }
    memset(t,0,sizeof(t));
    memset(f,0,sizeof(f));
    for (int i=1; i<=N; i++){
        for (int k=T; k>=v[i][0]; k--)
            t[i][k]=c[i][0];
        for (int j=1; j<=n[i]; j++)
            for (int k=T; k>=v[i][0]+v[i][j]; k--)
                t[i][k]=max(t[i][k],t[i][k-v[i][j]]+c[i][j]);  //第i个主件，k时间能拿到的最大经验值
    }
    for (int i=1; i<=N; i++)
        for (int j=T; j>=v[i][0]; j--)
            for (int k=j; k>=0; k--)
                f[j]=max(f[j],f[j-k]+t[i][k]);
    printf("%lld
", f[T]);
    return 0;
}