Hugo Ve Nha
unknown
java
a year ago
2.4 kB
8
Indexable
import java.io.FileInputStream; import java.io.FileNotFoundException; import java.util.Scanner; public class HugoVeNha { static int N; static int gate[][]; static int res; static int armyAtGate[], expAtGate[]; static void BT(int k, int cost){ if(k == N){ res = res < cost ? res : cost; return; } if(cost > res) return; //Pass BT(k+1, cost + gate[k][1]); //Hire armyAtGate[k] += gate[k][0]; BT(k+1, cost + gate[k][1]*2); armyAtGate[k] -= gate[k][0]; //Combat int total = 0; int tmp_army[] = new int[21]; int tmp_exp[] = new int[21]; for(int i = 0; i < k; i++){ tmp_army[i] = armyAtGate[i]; tmp_exp[i] = expAtGate[i]; if(armyAtGate[i] > 0 && expAtGate[i] < 3){ total += armyAtGate[i]; } } int enermy = gate[k][0]; if(total < enermy) return; for(int i = 0; i < k; i++){ if(armyAtGate[i] <= 0 || expAtGate[i] >= 3) continue; int tmp_enermy = enermy; enermy -= armyAtGate[i]; armyAtGate[i] -= tmp_enermy; if(enermy <= 0) break; } for(int i = 0; i < k; i++){ if(armyAtGate[i] > 0 || expAtGate[i] < 3) expAtGate[i] += 1; } BT(k+1, cost); for(int i = 0; i < k; i++){ armyAtGate[i] = tmp_army[i]; expAtGate[i] = tmp_exp[i]; } } public static void main(String[] args) { try { System.setIn(new FileInputStream("input_HugoVeNha.txt")); } catch (FileNotFoundException e) { e.printStackTrace(); } Scanner sc = new Scanner(System.in); int T = sc.nextInt(); for(int t = 1; t <= T; t++){ N = sc.nextInt(); gate = new int[21][2]; for(int i = 0; i < N; i++){ gate[i][0] = sc.nextInt(); gate[i][1] = sc.nextInt(); } //Solve res = 999999; armyAtGate = new int[21]; expAtGate = new int[21]; BT(0, 0); System.out.println("#" + t + " " + res); } } }
Editor is loading...
Leave a Comment