Untitled

 avatar
unknown
plain_text
2 years ago
1.6 kB
2
Indexable
#include <iostream>
using namespace std;
int N,M,L;
int listNM[100], listL[100];
int a[100][100];
long Answer;

void Try(int k, int pos, long min)
{
	int i,j;
	if(k == L)
	{
		if(Answer > min) Answer = min;
		return;
	}
	else
	{
		for(i = pos; i <= (N+M); i++)
		{
				if((min+listNM[i]) < Answer)
				{
						int tempK = k;
						for(j = 1; j <= a[i][0]; j++)
						{
							int temp = a[i][j];
							if(listL[temp] != -1)
							{
								listL[temp]++;
								if(listL[temp] == 1) tempK++;
							}
						}
						if(tempK > k)
							Try(tempK, i+1, min+listNM[i]);
						
						for(j = 1; j <= a[i][0]; j++)
						{
							int temp = a[i][j];
							if(listL[temp] != -1)
								listL[temp]--;
						}
				}

		}
	}
	return;
}

int main()
{
	freopen("Text.txt","r",stdin);

	int T;
	cin>>T;
	int i,j;
	for(int tc =1; tc <= T; tc++)
	{
		Answer = 1000000000;
		cin >> N;
		for(i = 1; i <= N; i++)
		{
			cin >> listNM[i]; // gia linh kien cho troi
			a[i][0] = 1; a[i][1] = i;//moi linh kien co 1 cai, cot la ten linh kien
		}

		cin >> M; // so luong combo
		for(i = 1; i <= M; i++)
		{
			cin >> listNM[N+i]; // gia cac combo
			cin >> a[N+i][0];   // so linh kien trong combo
			for(j = 1; j <= a[N+i][0]; j++)
				cin >> a[N+i][j];  // cac linh kien co trong combo
		}
		cin >>L;
		for(i = 1; i <= N; i++)
			listL[i] = -1;
		for(i = 1; i <= L; i++)
		{
			cin >> j;  //cac linh kien can mua
			listL[j] = 0;
		}
		
		Try(0,1,0);

		cout <<"#"<<tc<<" "<<Answer<<endl;
	}
	
	return 0; //Your program should return 0 on normal termination.
}