Untitled
unknown
plain_text
a year ago
1.2 kB
8
Indexable
#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; }
Editor is loading...
Leave a Comment