Untitled
unknown
plain_text
2 years ago
1.3 kB
7
Indexable
package HugoVeNha; import java.util.Scanner; public class test { static int N; static int[][] Door=new int[100][2]; static int[] linh=new int[3]; static int ans=0; static void backtrack(int k,int sum){ if(k==N){ if(sum<ans){ ans=sum; } return; } if(sum>ans){ return; } int Linh1=linh[0]; int Linh2=linh[1]; int Linh3=linh[2]; for(int i=0;i<3;i++){ if(i==0){ backtrack(k+1, sum+Door[k][1]); } else if(i==1) { linh[0]+=Door[k][0]; backtrack(k+1, sum+Door[k][1]*2); linh[0]=Linh1; } else { if(linh[0]+linh[1]+linh[2]>=Door[k][0]){ int tmp = Door[k][0]; for (int j = 2; j >= 0; j--) { if (tmp > linh[j]) { tmp -= linh[j]; linh[j] = 0; } else { linh[j] -= tmp; break; } } linh[2] = linh[1]; linh[1] = linh[0]; linh[0] = 0; backtrack(k + 1, sum); linh[0]=Linh1; linh[1]=Linh2; linh[2]=Linh3; } } } } public static void main(String[] args) { Scanner scanner=new Scanner(System.in); int tc=scanner.nextInt(); for(int i=0;i<tc;i++){ N=scanner.nextInt(); for(int j=0;j<N;j++){ for(int k=0;k<2;k++){ Door[j][k]=scanner.nextInt(); } } ans=9999999; backtrack(0, 0); System.out.println("#"+(i+1)+" "+ans); } } }
Editor is loading...