Untitled
unknown
plain_text
a year ago
2.2 kB
4
Indexable
import java.util.Scanner; public class Solution { public static int N, T, ans, temp, minStart, maxEnd, maxD; public static int[] L, P, A, D, visited, maxP; public static int[][] point; public static void main(String[] args) throws Exception { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); T = sc.nextInt(); for (int tc = 1; tc <= T; tc++) { N = sc.nextInt(); A = new int[N + 1]; D = new int[N + 1]; L = new int[4]; P = new int[4]; visited = new int[4]; point = new int[4][N + 1]; maxP = new int[N + 1]; for (int i = 1; i <= 3; i++) { L[i] = sc.nextInt(); } for (int i = 1; i <= 3; i++) { P[i] = sc.nextInt(); } minStart = 10000; maxEnd = 0; for (int i = 1; i <= N; i++) { A[i] = sc.nextInt(); D[i] = sc.nextInt(); if (minStart > A[i]) { minStart = A[i]; } if (maxD < D[i]) { maxD = D[i]; } } maxEnd = minStart + maxD; ans = 0; backTracking(1, minStart); System.out.println("Case #" + tc); System.out.println(ans); } } public static void backTracking(int k, int start) { if (k > 3) { temp = 0; maxP = new int[N+1]; for (int c = 1; c <= N; c++) { for (int r = 1; r <= 3; r++) { if (point[r][c] > maxP[c]) { maxP[c] = point[r][c]; } } } for (int i = 1; i <= N; i++) { temp += maxP[i]; // System.out.print(maxP[i] + " "); } // System.out.println(temp + "*"); if (temp > ans) { ans = temp; } return; } for (int i = 1; i <= 3; i++) { if (visited[i] == 0) { if (start + L[i] > maxEnd) { backTracking(k + 1, start); } else { for (int j = start; j <= maxEnd - L[i]; j++) { int cStart = j; int cEnd = cStart + L[i]; for (int m = 1; m <= N; m++) { if (A[m] <= cStart && A[m] + D[m] >= cEnd) { point[i][m] = P[i]; } } visited[i] = 1; backTracking(k + 1, cEnd); visited[i] = 0; for (int m = 1; m <= N; m++) { point[i][m] = 0; } } } } } } }
Editor is loading...
Leave a Comment