Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
1.1 kB
2
Indexable
Never
package TietKiemDien;

import java.util.Scanner;

public class test {
static int N,K;
static int[] TrangThai=new int[101];
static int ans=0;
static int SobongTat(){
	int sum=0;
	for(int i=1;i<=N;i++){
		if(TrangThai[i]==0){
			sum++;
		}
	}
	return sum;
}
static void backtrack(int k){
	if(SobongTat()>ans){
		ans=SobongTat();
	}
	if(k==3){
		return;
	}
	for(int i=1;i<=K;i++){
		for(int j=0;j<=(N-i)/(i+1);j++){
			if(TrangThai[i+j*(i+1)]==0){
				TrangThai[i+j*(i+1)]=1;			}
			else {
				TrangThai[i+j*(i+1)]=0;
			}
		}
		backtrack(k+1);
		for(int j=0;j<=(N-i)/(i+1);j++){
			if(TrangThai[i+j*(i+1)]==0){
				TrangThai[i+j*(i+1)]=1;			}
			else {
				TrangThai[i+j*(i+1)]=0;
			}
		}
	}
}

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();
		K=scanner.nextInt();
		for(int j=1;j<=N;j++){
			TrangThai[j]=scanner.nextInt();
		}
		ans=0;
		backtrack(0);
		System.out.println("#"+(i+1)+" "+ans);
	}
}
}