Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
1.6 kB
2
Indexable
Never
#include<iostream>
using namespace std;
int N,M;
int market[30];
int Mang[35][1000];
int price_combo[35];
int tb_combo[35];
int tbmt[20];
int sotb_canmua;
int combo_canmua[20];
int price=0;
int minn= 10000000;
void buy(int k)
{
	price += price_combo[k];
	for(int i=1; i<= tb_combo[k]; i++){
		tbmt[Mang[k][i]] ++;
	}
}
void unbuy(int k)
{
	price -= price_combo[k];
	for(int i=1; i<= tb_combo[k]; i++){
		tbmt[Mang[k][i]] --;
	}
}

void BT(int k)
{
	if(price >= minn) { return; }
	if(k==M+1 ) {
			int price_market=0;
			for(int i=1; i<=sotb_canmua; i++)
		    {
			if(tbmt[combo_canmua[i]] ==0){
				price_market += market[combo_canmua[i]];
				cout << price << " " << price_market << " " <<minn << endl;
				if(price_market + price >= minn) { break;}
			    }
		    }
		    if(price_market +price < minn) { minn = price_market +price ;}
		return;
	}
	for(int i=0; i<2; i++)
	{
		if(i==0) { BT(k+1); }
		if(i==1){
            buy(k);
			BT(k+1);
			unbuy(k);
		}
	}
}
int main()
{
	int t;
	cin >> t;
	for(int stt=1; stt <=t; stt++)
	{
		cin >> N;
		for(int i=1; i<=N; i++)
		{
			cin >> market[i];
			tbmt[i] =0;
		}
		cin >> M;
		for(int i=1; i<=M; i++)
		{
			cin >> price_combo[i] >> tb_combo[i];
			for(int j=1; j<= tb_combo[i]; j++)
			{
				cin >> Mang[i][j];
			}
		}
		cin >> sotb_canmua;
		for(int i=1; i<= sotb_canmua; i++)
		{
			cin >> combo_canmua[i];
		}
		//////////////////////////////////////////
		BT(1);
		//cout << price << endl;//
		cout << "#" << stt << " " << minn << endl;
		price  =0;
		minn =10000000;
	}
}