Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
2.2 kB
1
Indexable
Never
#include <iostream>
using namespace std;

int N;
int market[21];   // mua o cho troi
int onli[31][21]; // mua combo online
int cost[31]; // gia com bo
int cnt[31];
int lk[21]; // linh kien can mua
bool vs[21];

int pake; // soluong goi can mua
int nes;  // so linh kien can thiet

void reset()
{
	for(int i = 0; i < 21; i++)
	{
		market[i] = 0;
		lk[i] = 0;
	}
	for(int i = 0; i < 31; i++)
	{
		cost[i] = 0;
		cnt[i] = 0;
		for(int j = 0; j < 21; j++)
		{
			onli[i][j] = 0;
		}
	}
}

// neu mua online thieu mua o cho
int sm()
{
	int sum = 0;
	for(int i = 1; i <= N; i++)
	{
		if(lk[i] == 0 && vs[i] == true)
		{
			sum = sum + market[i];
		}
	}
	return sum;
}

void resetvs()
{
	for(int i = 0; i < 21; i++)
	{
		vs[i] = false;
	}
}
// giai thuat mua combo tren mang neu thieu mua o cho troi

void mua(int k)
{
	for(int i = 0; i < cnt[k]; i++)
	{
		lk[onli[k][i]]++;
	}
}

void ban(int k)
{
	for(int i = 0; i < cnt[k]; i++)
	{
		lk[onli[k][i]]--;
	}
}

void buy(int k, int &min, int sum)
{
	if(sum > min)
	{
		return;
	}
	if(k == pake)
	{
		int t = sm();
	    if(min > sum + t)
	    {
		    min = sum + t;
	    }
		return;
	}
	for(int i = 0; i <= 1; i++)
	{
		if(i == 0)
		{
			// khong mua goi thu k
			buy(k + 1, min, sum);
		}
		else
		{
			mua(k);
			buy(k + 1, min,sum + cost[k]);
			ban(k);
		}
	}
}


int main()
{
	freopen("input.txt", "r", stdin);
	int testcase;
	cin >> testcase;
	for(int tc = 1; tc <= testcase; tc++)
	{
		cin >> N;
		reset();
		resetvs();
		for(int i = 1; i <= N; i++)
		{
			cin >> market[i];
		}
		// mua theo goi tren mang
		cin >> pake;
		for(int i = 0; i < pake; i++)
		{
			cin >> cost[i] >> cnt[i];
			for(int j = 0; j < cnt[i]; j++)
			{
				cin >> onli[i][j];
			}
		}
		// link kien can thiet
		cin >> nes;
		for(int i = 1; i <= nes; i++)
		{
			int x;
			cin >> x;
			vs[x] = true;
		}
		int min = 1000000;
		buy(0, min, 0);
		cout<<"#"<<tc<<" "<<min<<endl;
	}
	return 0;
}

10
68 63 83 94 55 35 12 63 30 17 
4
104 3 2 6 3 
31 3 2 5 3 
81 4 3 2 7 9 
42 1 7 
6 9 10 3 8 6 5 
4
40 52 12 94 
2
58 2 1 4 
15 1 2 
3 4 2 3 


#1 176
#2 85