Untitled
unknown
plain_text
a year ago
1.5 kB
3
Indexable
public class Solution { static int T, g; static int gate[][], min; static int sg[], count[]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); T = sc.nextInt(); for (int tc = 1; tc <= T; tc++) { g = sc.nextInt(); gate = new int[g][2]; for (int i = 0; i < g; i++) { gate[i][0] = sc.nextInt(); gate[i][1] = sc.nextInt(); } min = 123456789; sg = new int[g]; count = new int[g]; backTrack(0, 0); System.out.println("#" + tc + " " + min); } } public static void backTrack(int k, int sum) { if (sum >= min) return; if (k == g) { if (sum < min) min = sum; return; } backTrack(k + 1, sum + gate[k][1]); sg[k] += gate[k][0]; backTrack(k + 1, sum + 2 * gate[k][1]); sg[k] -= gate[k][0]; int number = 0; int tc[] = new int[21]; int ts[] = new int[21]; for (int i = 0; i < k; i++) { tc[i] = count[i]; ts[i] = sg[i]; if (tc[i] < 3 && ts[i] > 0) number += sg[i]; } if (number < gate[k][0]) return; int ss = gate[k][0]; for (int i = 0; i < k; i++) { if (count[i] >= 3 || sg[i] <= 0) continue; int m = ss; ss -= sg[i]; sg[i] -= m; if (ss <= 0) break; } for (int i = 0; i < k; i++) { if (count[i] < 3 && sg[i] > 0) count[i]++; } backTrack(k + 1, sum); for (int i = 0; i < k; i++) { count[i] = tc[i]; sg[i] = ts[i]; } } }
Editor is loading...
Leave a Comment