Untitled

mail@pastecode.io avatar
unknown
plain_text
11 days ago
1.4 kB
0
Indexable
Never
#include<iostream>
using namespace std;
int nTestcase, N, Max;
int bongbay[11];
int visited[11];

int pointLeft(int start){
	for(int i = start - 1; i >= 0; i--){
		if(visited[i] == 0) return bongbay[i];
	}
	return 0;
}

int pointRight(int start){
	for(int i = start + 1; i < N; i++){
		if(visited[i] == 0) return bongbay[i];
	}
	return 0;
}

void backtrack(int nB, int sum){
	if(nB == N - 2){
		int temp = 0;
		for(int i = 0; i < N; i++){
			if(visited[i] == 0 && bongbay[i] > temp) temp = bongbay[i] ;
		}
		sum += 2*temp;
		if(sum > Max){
			Max = sum;
			sum -= 2*temp;
		}
		return;
	}
	for(int i = 0; i < N; i++){
		if(visited[i] == 0){
			visited[i] = 1;
			int left = pointLeft(i);
			int right = pointRight(i);
			int point;
			if(left == 0 && right != 0){
				point = right;
			}else if(right == 0 && left != 0){
				point = left;
			}else if(right == 0 && left == 0){
				point = bongbay[i];
			}else{
				point = left*right;
			}
			backtrack(nB+1, sum + point);			
			visited[i] = 0;
		}
	}
}

int main(){
	freopen("input.txt","r",stdin);
	cin >> nTestcase;
	for(int testcase = 1; testcase <= nTestcase; testcase++){
		cin >> N;
		for(int i = 0; i < N; i++){
			cin >> bongbay[i];
		}
		Max = 0;
		backtrack(0,0);
		cout << "Case #" << testcase << endl << Max << endl;
	}
	return 0;
}
Leave a Comment