Untitled
package Bai1; import java.io.FileInputStream; import java.util.Scanner; public class HugoAds { static int noV; static int[][] ads = new int[3][2]; static int[][] info = new int[3][2]; static int[][] vis = new int[51][2]; static int[] visit = new int[100]; static int max; static int maxleft; static boolean check(int s, int id){ for(int i = s; i < s + ads[id][0]; i++){ if (visit[i] != -1) return false; } return true; } static int checkPoint(){ int sum = 0; for (int i = 0; i < noV; i++){ int point; int maxpoint = 0; int a = vis[i][0]; int d = vis[i][1]; for (int j = 0; j < 3; j++){ int a1 = info[j][0]; int d1 = info[j][1]; if (a <= a1 && d >= d1){ point = ads[j][1]; if (point > maxpoint) maxpoint = point; } } sum += maxpoint; } return sum; } static void backtrack(int id){ if (id == 3){ int point = checkPoint(); if (point > max) max = point; return; } for(int i = 1; i <= maxleft; i++){ if (!check(i, id)) continue; for (int j = i; j < i + ads[id][0]; j++){ visit[j] = 1; } info[id][0] = i; info[id][1] = ads[id][0] + i; backtrack(id+1); for (int j = i; j < i + ads[id][0]; j++){ visit[j] = -1; } info[id][0] = 0; info[id][1] = 0; } } public static void main(String[] args) throws Exception{ // TODO Auto-generated method stub System.setIn(new FileInputStream("input.txt")); Scanner sc = new Scanner(System.in); int T = sc.nextInt(); for (int tc = 1; tc <= T; tc++){ noV = sc.nextInt(); for (int i = 0; i < 3; i++){ ads[i][0] = sc.nextInt(); //length } for (int i = 0; i < 3; i++){ ads[i][1] = sc.nextInt(); //point } maxleft = 0; for(int i = 0; i < 100; i++){ visit[i] = -1; } for (int i = 0; i < noV; i++){ int a = sc.nextInt(); int d = sc.nextInt(); vis[i][0] = a; vis[i][1] = a + d; if(vis[i][1] > maxleft) maxleft = vis[i][1]; //System.out.println(maxleft); } max = 0; backtrack(0); System.out.println("Case #" + tc + "\n" + max); } } }
Leave a Comment