Untitled

mail@pastecode.io avatar
unknown
plain_text
10 days ago
2.3 kB
1
Indexable
Never
import java.util.Scanner;

public class Main {
    static int N, M, L;
    static int[] prices;
    static int[][] offers;
    static int[] needed;
    static int minCost;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();

        for (int t = 0; t < T; t++) {
            N = sc.nextInt();
            prices = new int[N];
            for (int i = 0; i < N; i++) {
                prices[i] = sc.nextInt();
            }

            M = sc.nextInt();
            offers = new int[M][];
            for (int i = 0; i < M; i++) {
                int P = sc.nextInt();
                int K = sc.nextInt();
                offers[i] = new int[K + 1];
                offers[i][0] = P;
                for (int j = 1; j <= K; j++) {
                    offers[i][j] = sc.nextInt() - 1;
                }
            }

            L = sc.nextInt();
            needed = new int[N];
            for (int i = 0; i < L; i++) {
                needed[sc.nextInt() - 1]++;
            }

            minCost = Integer.MAX_VALUE;
            backtrack(0, new int[N], 0);

            System.out.println("#" + (t + 1) + " " + minCost);
        }

        sc.close();
    }

    private static void backtrack(int currentCost, int[] bought, int offerIndex) {
        if (currentCost >= minCost) {
            return;
        }

        if (allNeededBought(bought)) {
            minCost = Math.min(minCost, currentCost);
            return;
        }

        for (int i = 0; i < N; i++) {
            if (bought[i] < needed[i]) {
                bought[i]++;
                backtrack(currentCost + prices[i], bought, offerIndex);
                bought[i]--;
            }
        }

        for (int i = offerIndex; i < M; i++) {
            int cost = offers[i][0];
            for (int j = 1; j < offers[i].length; j++) {
                bought[offers[i][j]]++;
            }
            backtrack(currentCost + cost, bought, i);
            for (int j = 1; j < offers[i].length; j++) {
                bought[offers[i][j]]--;
            }
        }
    }

    private static boolean allNeededBought(int[] bought) {
        for (int i = 0; i < N; i++) {
            if (bought[i] < needed[i]) {
                return false;
            }
        }
        return true;
    }
}
Leave a Comment