记录编号	74729	评测结果	AAAAAAAAAAAA
题目名称	商店购物	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.058 s
提交时间	2013-10-26 10:07:42	内存使用	0.38 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
const int SIZEID=1050;
const int SIZESALE=200;
const int SIZEGOAL=7;
int lis[SIZEID]={0};//lisp[i]表示i是购买清单上的第几号
int s;
vector<pair<int,int> > sale[SIZESALE];//存放促销活动
//first是商品,second是数量
int sale_price[SIZESALE];
bool able[SIZESALE]={0};
int b;
int goal_id[SIZEGOAL]={0};
int goal_num[SIZEGOAL]={0};//不买的商品自动初始化为0个
bool in_list(int x){//第x个促销的商品是否全在购物清单中,若否则
	int i,j;
	int c;
	bool flag;
	for(i=0;i<sale[x].size();i++){
		c=sale[x][i].first;
		flag=false;
		for(j=1;j<=b;j++){
			if(c==goal_id[j]){
				flag=true;
				break;
			}
		}
		if(!flag) return false;
	}
	return true;
}
void init(void){
	scanf("%d",&s);
	int i,j,km,n;
	int c,k;
	for(i=1;i<=s;i++){
		scanf("%d",&n);
		for(j=1;j<=n;j++){
			scanf("%d%d",&c,&k);//k个编号c的商品
			sale[i].push_back(make_pair(c,k));
		}
		scanf("%d",&sale_price[i]);
	}
	scanf("%d",&b);
	for(i=1;i<=b;i++){
		scanf("%d%d",&c,&k);
		lis[c]=i;
		goal_id[i]=c;
		goal_num[i]=k;
		sale[s+i].push_back(make_pair(c,1));
		scanf("%d",&sale_price[s+i]);
	}
	s+=b;
	for(i=1;i<=s;i++) able[i]=in_list(i);
}
int f[SIZEGOAL][SIZEGOAL][SIZEGOAL][SIZEGOAL][SIZEGOAL]={0};
bool legal(int i1,int i2,int i3,int i4,int i5,int x){//x号促销加上去是否超过范围
	int i;
	int id,k;
	for(i=0;i<sale[x].size();i++){
		id=lis[sale[x][i].first];
		k=sale[x][i].second;
		if(id==1&&k+i1>goal_num[1]) return false;
		else if(id==2&&k+i2>goal_num[2]) return false;
		else if(id==3&&k+i3>goal_num[3]) return false;
		else if(id==4&&k+i4>goal_num[4]) return false;
		else if(id==5&&k+i5>goal_num[5]) return false;
	}
	return true;
}
void relax(int i1,int i2,int i3,int i4,int i5,int x){//对活动x进行扩展
	int i;
	int k,id;
	int a1=i1,a2=i2,a3=i3,a4=i4,a5=i5;
	for(i=0;i<sale[x].size();i++){
		id=lis[sale[x][i].first],k=sale[x][i].second;
		if(id==1) a1=i1+k;
		else if(id==2) a2=i2+k;
		else if(id==3) a3=i3+k;
		else if(id==4) a4=i4+k;
		else if(id==5) a5=i5+k;
	}
	f[a1][a2][a3][a4][a5]=min(f[a1][a2][a3][a4][a5],f[i1][i2][i3][i4][i5]+sale_price[x]);
}
void try_extend(int i1,int i2,int i3,int i4,int i5){
	int i;
	for(i=1;i<=s;i++){
		if(!legal(i1,i2,i3,i4,i5,i)) continue;
		relax(i1,i2,i3,i4,i5,i);
	}
}
void dp(void){
	int i1,i2,i3,i4,i5;
	for(i1=0;i1<=goal_num[1];i1++){
		for(i2=0;i2<=goal_num[2];i2++){
			for(i3=0;i3<=goal_num[3];i3++){
				for(i4=0;i4<=goal_num[4];i4++){
					for(i5=0;i5<=goal_num[5];i5++){
						f[i1][i2][i3][i4][i5]=0x7ffffff;
					}
				}
			}
		}
	}
	f[0][0][0][0][0]=0;
	for(i1=0;i1<=goal_num[1];i1++){
		for(i2=0;i2<=goal_num[2];i2++){
			for(i3=0;i3<=goal_num[3];i3++){
				for(i4=0;i4<=goal_num[4];i4++){
					for(i5=0;i5<=goal_num[5];i5++){
						try_extend(i1,i2,i3,i4,i5);
					}
				}
			}
		}
	}
}
int ans(void){
	int a1,a2,a3,a4,a5;
	a1=goal_num[1];
	a2=goal_num[2];
	a3=goal_num[3];
	a4=goal_num[4];
	a5=goal_num[5];
	return f[a1][a2][a3][a4][a5];
}
int main(){
	freopen("shoppingus.in","r",stdin);
	freopen("shoppingus.out","w",stdout);
	init();
	dp();
	printf("%d\n",ans());
	return 0;
}