Untitled

mail@pastecode.io avatar
unknown
plain_text
2 months ago
1.2 kB
5
Indexable
Never
#include<iostream>
using namespace std;

int T, N, arr[100], visited[100];
int sum, Answer;

void reset(){
	for(int i = 0; i <= N + 1; i++){
		visited[i] = 0;
	}
}

bool duyetHet(){
	for(int i =1; i <= N; i++){
		if(visited[i] == 0){
			return false;
		}
	}
	return true;
}

void backtrack(int k){
	if(visited[k] == 1){
		return;
	}
	//cout << k << " ";
	visited[k] = 1;
	if( duyetHet() ){
		sum += arr[k];
		if(Answer < sum){
			Answer = sum;
		}
		return;
	}
	else{
		int a=0, b=0;
		for(int i = k; i<= N+1; i++){
			if(visited[i] == 0) {
				a = arr[i];
				break;
			}			
		}
		for(int i = k; i >= 0; i--){
			if(visited[i] == 0){
				b = arr[i];
				break;
			}
		}
		sum += a * b;
	}
	for(int i = 1; i<= N; i++){
		int m = sum;
		if(visited[i] == 0){
			backtrack(i);
		}
		visited[k] = 0;
		sum = m;
			
	}
	
}

int main(){
	freopen("BanSo.txt", "r", stdin);
	cin >> T;
	for(int tc = 1; tc <= T; tc++){
		Answer = 0;
		cin >> N;
		for(int i = 1; i <= N; i++){
			cin >> arr[i];
		}
		arr[0] = 1;
		arr[N+1] = 1;

		for(int i = 1; i <= N; i++){
			sum = 0;
			reset();	
			backtrack(i);
		}
		cout << "#" << tc << " " << Answer << endl;
	}
	return 0;
}
Leave a Comment