Untitled

mail@pastecode.io avatarunknown
plain_text
a month ago
1.6 kB
4
Indexable
Never
#include<iostream>
using namespace std;
const int MaxL = 15;
int T, N, a[MaxL], re, v[MaxL], start, endc;

int getDiem(int k) {
	int index1 = k + 1;
	while (index1 < endc) {
		if(v[index1] == 0) break;
		index1++;
	}
	int index2 = k - 1;
	while (index2 >= start) {
		if(v[index2] == 0) break;
		index2--;
	}
	if(index1 != endc && index2 != start - 1)
		return a[index1] * a[index2];
	else if(index1 != endc)
		return a[index1];
	else if(index2 != start - 1)
		return a[index2];
	else
		return a[k];
}

void doing(int k, int c) {
	if(k == endc - start - 2) {
		if(c > re)
			re = c;
		return;
	}
	for(int i = start; i <endc - 2;i++) {
		if(v[i + 1] == 0) {
			v[i + 1] = 1;
			doing(k + 1, c + getDiem(i + 1));
			v[i + 1] = 0;
		}
	}
};


void input() {
	cin >> N;
	for(int i = 0; i < N; i++) {
		cin >> a[i];
	}
}

int main() {
	/*freopen("input.txt", "r", stdin);*/
	cin >> T;
	for(int t = 0; t < T; t++) {
		input();
		start = 0, endc = N;
		re = 0;
		fill_n(v, N, 0);
		int i1 = 0, c1 = 0, sum = 0;
		while(i1 < N && a[i1] == 1) {
			c1++;
			i1++;
		}
		if(i1 != N) {
			sum += a[i1] * c1;
		}

		int i2 = N - 1, c2 = 0;
		while(i2 >= 0 && a[i2] == 1) {
			c2++;
			i2--;
		}
		if(i2 != -1) {
			sum += a[i2] * c2;
		}
		if(i1 != N && i2 != -1) {
			start = i1, endc = i2 + 1;
			for(int i = 0; i < start; i++) {
				v[i] = 1;
			}
			for(int i = N - 1; i >= endc; i--) {
				v[i] = 1;
			}
		}

		int tmp = a[start] > a[endc - 1] ? a[start] * 2 : a[endc - 1] * 2;
		doing(0, tmp + sum);
		cout << "Case #" << t + 1 << endl << re << endl;
	}
	return 0;
}