Untitled
plain_text
a month ago
2.7 kB
0
Indexable
Never
import java.io.FileInputStream; import java.io.FileNotFoundException; import java.util.Scanner; public class CopyOfArrayGame2 { static{ try { System.setIn(new FileInputStream("src/inp.txt")); // System.setOut(new PrintStream("src/out.txt")); } catch (FileNotFoundException e) { // TODO Auto-generated catch block e.printStackTrace(); } } static Scanner scanner=new Scanner(System.in); static class Node{ long sum; int i; int n; int res; Node link; Node(long s,int i,int n,int r){ this.sum=s; this.i=i; this.n=n; this.res=r; } } static class Stack{ Node front; int n; void push(Node node){ ++n; node.link=front; front=node; } void pop(){ if(front==null) return; --n; front=front.link; } } /*DUNG STACK LAM DE QUY, MOI THAM SO HAM DE QUY TUONG UNG VOI 1 STACK * static void run(long sum,int i,int n,int res) ... * static void run(Stack stack) { long sum=stack.front.sum; int i=stack.front.i; int n=stack.front.n; int res=stack.front.res; stack.pop(); Res=Math.max(Res,res); if(i>=n || (sum&1)>0) return; long s1=sum; long s2=0; for(int j=i;j<=n;++j) { s1-=a[j]; s2+=a[j]; if(s1==s2){ stack.push(new Node(s1,i,j,res+1)); stack.push(new Node(s2,j+1,n,res+1)); return; } } } * */ static void exec() { int n=Integer.parseInt(scanner.next()); int[] a=new int[n]; long Res=0,s=0; for(int i=0;i<n;++i){ a[i]=Integer.parseInt(scanner.next()); s+=a[i]; } Stack stack=new Stack(); stack.push(new Node(s,0,n-1,0));//so diem ban dau =0 while(stack.n>0){ long sum=stack.front.sum; int left=stack.front.i; int right=stack.front.n; int res=stack.front.res; stack.pop(); Res=Math.max(Res,res);//note cai nay phai de tren dieu kien if(left>=right || (sum&1)>0) do tinh ca truong hop tong la so am thi ko chia dc if(left>=right || (sum&1)>0) continue; long s1=sum;//tong ben phai long s2=0; //tong ben trai for(int j=left;j<=right;++j) { s1-=a[j];//o phan tu j hien tai thi bo di a[j] o ben phai, de cho vao ben trai s2+=a[j]; if(s1==s2){//2 ben bang nhau stack.push(new Node(s1,left,j,res+1));//moi lan chia dc tang 1 diem, sau do lai tiep tuc voi ben trai, phai sai khi chia dc stack.push(new Node(s2,j+1,right,res+1)); break; } } } System.out.println(Res); } public static void main(String[] args) { int t=Integer.parseInt(scanner.nextLine()); for(int test=1;test<=t;++test) exec(); scanner.close(); } }