Untitled
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