Untitled

mail@pastecode.io avatar
unknown
plain_text
7 months ago
1.0 kB
1
Indexable
Never
#include <iostream>
#define max(a, b) (a > b) ? a : b
using namespace std;
int off;
int T, N, K;
int arr[105];
int ans;
int key[12][100];

void change(int x){
	for(int i = 1; i <= key[x][0]; i++){
		if(arr[key[x][i]] == 1){
			arr[key[x][i]] == 0;
			off++;
		}else{
			arr[key[x][i]] == 1;
			off--;
		}
	}
}

void backtrack(int k){
	if(k > 3) return;

	ans = max(ans, off);

	for(int i = 1; i <= K; i++){
		change(i);
		backtrack(k + 1);
		change(i);
	}
}

int main(){
	freopen("input.txt", "rt", stdin);
	cin >> T;
	for(int tc = 1; tc <= T; tc++){
		cin >> N >> K;
		off = 0;
		for(int i = 1; i <= N; i++){
			cin >> arr[i];
			if(arr[i] == 0){
				off++;
			}
		}

		for(int i = 1; i <= K; i++){
			int cnt = 0;
			for(int j = 0; j < N; j++){
				if(i + j * (i + 1) <= N){
					key[i][j + 1] = i + j * (i + 1);
					cnt++;
				}
			}
			key[i][0] = cnt;
		}
		ans = off;
		backtrack(0);
		cout << "#" << tc << " " << ans << endl;
	}
	return 0;
}
Leave a Comment