Untitled

 avatar
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