Untitled
unknown
plain_text
a year ago
1.6 kB
7
Indexable
package OT; import java.io.FileInputStream; import java.io.FileNotFoundException; import java.util.Scanner; public class HugoComeHome { static int n, arr[][], s0, s1, s2, min, ans; static void backtrack(int k, int csum) { int add; add = 0; if (csum >= min) { return; } if (k == n) { min = Math.min(min, csum); return; } for (int i = 0; i < 3; i++) { if (i == 0) { add = arr[k][1]; backtrack(k + 1, csum + add); } else if (i == 1) { add = 2 * arr[k][1]; s0 += arr[k][0]; backtrack(k + 1, csum + add); s0 -= arr[k][0]; } else { int t2 = s2, t1 = s1, t0 = s0; int total = arr[k][0]; if (s0 + s1 + s2 >= total) { if (s2 >= total) { s2 = s1; s1 = s0; s0 = 0; } else if (s2 + s1 >= total) { s2 = s2 + s1 - total; s1 = s0; s0 = 0; } else { s1 = s2 + s1 + s0 - total; s2 = 0; s0 = 0; } backtrack(k + 1, csum); s2 = t2; s1 = t1; s0 = t0; } } } } public static void main(String[] args) throws FileNotFoundException { System.setIn(new FileInputStream("Input.txt")); Scanner scanner = new Scanner(System.in); int tc = scanner.nextInt(); for (int Case = 1; Case <= tc; Case++) { n = scanner.nextInt(); arr = new int[n][2]; for (int i = 0; i < n; i++) { arr[i][0] = scanner.nextInt(); arr[i][1] = scanner.nextInt(); } min = Integer.MAX_VALUE; s0 = s1 = s2 = 0; backtrack(0, 0); System.out.println("#" + Case + " " + min); } } }
Editor is loading...
Leave a Comment