Untitled

unknown
plain_text
10 months ago
2.5 kB
1
Indexable
Never
import java.util.Scanner;

public class Solution {
static int n;								// so mon do co san
static int[] price = new int[20];
static int m;								// so goi sale co san
static int[][] sale = new int[30][20];		// mon do co trong tung goi sale
static int[] salePrice = new int[30];		// gia sale tung goi
static int need;							// so mon do can mua
static int[] list = new int[20];			// danh sach can mua
static int[] visit = new int[20];			// da mua
static int bought;
static int min;
static int sum;

static int match(int j){
int count = 0;
for (int i = 0; i < 20; i++){
for (int k = 0; k < need; k++){
if (sale[j][i] == list[k] && visit[list[k]] == 0){
count++;
}
}
}
return count;
}

static void solve(int t, int g){
if (sum > min){
return;
}
if (t == need){
min = sum < min ? sum : min;
return;
}
for (int x = 0; x < 2; x++){
if (x == 1){
for (int i = 0; i < need; i++){
if(visit[list[i]] == 0){
visit[list[i]] = 1;
sum += price[list[i]];
solve(t+1, g);
visit[list[i]] = 0;
sum -= price[list[i]];
break;
}
}
}
else{
for (int j = g; j < m; j++){
int mat = match(j);
if (mat != 0){
sum +=  salePrice[j];
for (int k = 0; k < 20; k++){
if (sale[j][k] == -1)	break;
visit[sale[j][k]]++;
}
solve(t+mat, j);
sum -=  salePrice[j];
for (int k = 0; k < 20; k++){
if (sale[j][k] == -1)	break;
visit[sale[j][k]]--;
}
}
}
}
}
return;
}

public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner (System.in);
int T = sc.nextInt();
for (int tc = 1; tc <= T; tc++){

n = sc.nextInt();
min = 99999;
sum = 0;
for (int i = 0; i < 30; i++){
for (int j = 0; j < 20; j++){
sale[i][j] = -1;
list[j] = -1;
}
}
for (int i = 0; i < n; i++){
price[i] = sc.nextInt();
}
m = sc.nextInt();
for (int j = 0; j < m; j++){
salePrice[j] = sc.nextInt();
int a = sc.nextInt();
for (int k = 0; k < a; k++){
sale[j][k] = sc.nextInt()-1;
}
}

need = sc.nextInt();
for (int i = 0; i < need; i++){
list[i] = sc.nextInt()-1;
}
solve(0, 0);
System.out.println("#" + tc + " " + min);
}
}

}