记录编号	597266	评测结果	AAAAAAAAA
题目名称	4070.夏娜的菠萝包	最终得分	100
用户昵称	dick	是否通过	通过
代码语言	C++	运行时间	0.462 s
提交时间	2024-11-25 21:22:32	内存使用	6.48 MiB

    #include<bits/stdc++.h>
    using namespace std;
    int T;
    int n,m;
    const int MAXN=105; 
    struct edge{
    	int v;
    	int d;
    }e[MAXN];
    int sum[MAXN];
    int t[MAXN];
    int de[MAXN];
    int E[MAXN];
    int k[MAXN];
    int s[MAXN];
    int v[MAXN][MAXN];
    int p[MAXN];
    int maxx;
    int f[(1<<15)+5][25];
    int main(){
    	freopen("shana.in","r",stdin);
    	freopen("shana.out","w",stdout);
    	while(cin>>n){
    		if(n==0) break;
    		p[0]=1;
    		for(int i=1;i<=n;i++){
    			p[i]=p[i-1]*2;
    		}
    		memset(t,0x3f,sizeof(t));
    		memset(de,0,sizeof(de));
    		memset(sum,0,sizeof(sum));
    		memset(f,0,sizeof(f));
    		memset(s,0,sizeof(s));
    		for(int i=1;i<=n;i++){
    			cin>>e[i].v>>e[i].d;
    		}
    		cin>>m;
    		for(int i=1;i<=m;i++){
    			cin>>k[i]>>E[i];
    			for(int j=1;j<=k[i];j++){
    				int num;
    				cin>>num;
    				s[i]+=p[num-1];
    				sum[i]+=e[num].v;
    				de[i]+=e[num].d;
    				t[i]=min(t[i],e[num].v/e[num].d+1);
    			}
    			sum[i]+=E[i];
    		}
    		for(int i=1;i<=m;i++){
    			for(int j=1;j<=n;j++){
    				if(j>t[i]) v[i][j]=-1061109567;
    				else
    				v[i][j]=sum[i]-de[i]*(j-1);
    			}
    		}
    		for(int i=1;i<=p[n]-1;i++){
    			for(int j=1;j<=n;j++){
    				for(int h=1;h<=m;h++){
    					if((i&s[h])==s[h]){
    						f[i][j]=max(max(f[i][j],f[i][j-1]),f[(i-s[h])][j-1]+v[h][j]);
    					} 
    				}
    			}
    		}
    		for(int i=1;i<=p[n]-1;i++){
    			maxx=max(maxx,f[i][n]);
    		}
    		cout<<maxx<<endl;
    		maxx=0;
    	}
     
    	return 0;
    }