这题和NOIP的金明的预算方案(?)很像,只不过附件的数量增多了
如果对主件进行一次01背包,再套一层附件的01背包O(n4)肯定会爆。。
所以我们可以先预处理出,对于每个主件,花的时间为k的情况下,最大的经验值,用01背包做
然后再对每个主件进行01背包,这样就去掉了一层循环
#include<stdio.h> #include<string.h> #include<algorithm> #define maxn 102 using namespace std; ],v[maxn][maxn*],c[maxn][maxn*],t[maxn][maxn*],f[maxn*]; int N,T; int main(){ scanf("%d%d", &N, &T); ; i<=N; i++){ scanf(], &c[i][]); ; j<=n[i]; j++) scanf("%lld%lld", &v[i][j], &c[i][j]); } memset(t,,sizeof(t)); memset(f,,sizeof(f)); ; i<=N; i++){ ]; k--) t[i][k]=c[i][]; ; j<=n[i]; j++) ]+v[i][j]; k--) t[i][k]=max(t[i][k],t[i][k-v[i][j]]+c[i][j]); //第i个主件,k时间能拿到的最大经验值 } ; i<=N; i++) ]; j--) ; k--) f[j]=max(f[j],f[j-k]+t[i][k]); printf("%lld\n", f[T]); ; }