I love exam 01背包+分组背包

题目链接
题目大意：
有n个学科需要考试，每门学科有mi种复习材料，每个材料需要花费v天来阅读，得到w的分数，每门课得分上限为100分。你还有t天的复习时间，最多可以挂p门课的前提下最多可以的多少分。
总体思路：
对每门课的所有复习材料做01背包，f[i][j]表示第i门课花费j天最多可以获得多少分数，每一门课f[i][j]看作一组物品，每组物品至多是能选一个，再做一个分组背包。g[i][j][k]表示前i门课，在挂j门课的前提下，第k天最多可以的多少分。这里i这一维不可以省略，因为我们最后全为负无穷表示挂科数超过P输出-1。

#include<bits/stdc++.h>
using namespace std;
int T;
int n,m;
int t,p;
int v,w;
struct ty{
    int v,w;
};
vector<ty > a[55];
string x;
int c[55];//记录每门课一共可以看多少天
int f[55][505];
int g[55][5][505]; 
map<string ,int > mp;
int main(){
    scanf(" %d",&T);
    while(T--){
        memset(f,-0x3f,sizeof(f));
        memset(g,-0x3f,sizeof(g));
        memset(c,0,sizeof(c));
        scanf(" %d",&n);
        for(int i=0;i<=n+1;i++) a[i].clear();
        for(int i=0;i<=n+1;i++) f[i][0]=0;
        for(int i=1;i<=n;i++){
            cin>>x;
            mp[x]=i;
        }
        scanf(" %d",&m);
        for(int i=1;i<=m;i++){
            cin>>x;
            scanf(" %d %d",&w,&v);
            c[mp[x]]+=v;
            ty tt;
            tt.v=v; tt.w=w;
            a[mp[x]].push_back(tt);
        }
        scanf(" %d %d",&t,&p);
        for(int i=1;i<=n;i++){
            int len=a[i].size();
            for(int j=0;j<len;j++){
                for(int k=min(c[i],t);k>=a[i][j].v;k--){
                    f[i][k]=max(f[i][k],min(f[i][k-a[i][j].v]+a[i][j].w,100));
                }
            }
        }
        g[0][0][0]=0;
//注意g的初始化，只能初始化g[0][0][0]=0，不能初始化g[i][0][0]为0
//因为如果第二门课去不及格且不及格数为1的情况下一个是第一门课取及格的基础上，
//如果g[1][0][0]=0的化，相当于第一门课也取了不及格，和总不及格数为1相矛盾，g[1][0][0]初始化为负无穷可以排除这种错误
        for(int i=1;i<=n;i++){
            for(int j=0;j<=p;j++){
                for(int k=t;k>=0;k--){//枚举天数 
                    //g[i][j][k]=g[i-1][j][k];//这一步不可以要，不然就相当于取掉了第一维
                    for(int l=0;l<=c[i];l++){//枚举每一组中的物品
                        if(k>=l){
                            if(f[i][l]>=60) g[i][j][k]=max(g[i][j][k],g[i-1][j][k-l]+f[i][l]);
                            else if(f[i][l]<60&&j>0) g[i][j][k]=max(g[i][j][k],g[i-1][j-1][k-l]+f[i][l]);
                        }         
                    }
                }
            }
        }
        int ans=0;
        for(int i=0;i<=p;i++){
            ans=max(ans,g[n][i][t]);
        }
        if(ans==0) printf("-1\n");
        else printf("%d\n",ans);
    }
    return 0;
}