Untitled
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; }