1 #include <iostream>
2 #include <algorithm>
3 #include <cstring>
4 using namespace std;
5 const int b=6;//进制
6 int B[15];
7 int mapp[1010];// id 映射
8 int val[200];// 价值
9 int cost[200];// 花费
10 int dp[66666];//状态下的最小花费
11 int n,m,goal;// goal 最终的状态
12 bool cmp (int x,int y) {
13 for (int i=0;i<n;i++) {
14 int tx=x%b;
15 int ty=y%b;
16 if (tx<ty) return false;
17 x/=b;
18 y/=b;
19 }
20 return true;
21 }
22 int main ()
23 {
24 ios::sync_with_stdio(false);
25 B[0]=1;
26 for (int i=1;i<=10;i++) B[i]=B[i-1]*b;
27 cin>>n;
28 for (int i=0;i<n;i++) {// 单价也看做是一种更新方案
29 int id,num;
30 cin>>id>>num>>val[i];
31 mapp[id]=i;
32 cost[i]=B[i];// i 从0开始
33 goal+=cost[i]*num;
34 }
35 cin>>m;
36 for (int i=n;i<n+m;i++) {
37 int t; cin>>t;
38 int state=0;
39 for (int j=1;j<=t;j++) {
40 int id,num;
41 cin>>id>>num;
42 state+=cost[mapp[id]]*num;
43 }
44 cost[i]=state;// 优惠方案的cost
45 cin>>val[i];
46 }
47 memset (dp,0x3f,sizeof(dp)); dp[0]=0;
48 for (int i=0;i<n+m;i++)
49 for (int j=cost[i];j<=goal;j++) {
50 if (cmp (j,cost[i]))// 更新的时候 判断各个物品是否大于cost[i](能否更新)
51 dp[j]=min (dp[j],dp[j-cost[i]]+val[i]);
52 }
53 cout<<dp[goal]<<endl;
54 return 0;
55 }
