Untitled
unknown
plain_text
a year ago
1.2 kB
3
Indexable
#include<iostream> using namespace std; int T,N,a[1001],visited[1001],s[1001],visited2[1001],res,sum; void xuat(){ for (int i=1 ;i<=N-2;i++){ cout<<s[i]<<" "; } cout<<endl; } void reset(){ for (int i=1 ;i<=N+1;i++){ visited2[i]=0; } } int getMax(){ int max=-1; for (int i=1;i<=N;i++){ if(!visited2[i]){ if(max<a[i]) max=a[i]; } } return max; } int tinh(int k){ int sum=0; //1 2 3 4 5 6 7 8 //duyet het s[]; for (int i=1 ;i<=N-2;i++){ int idx=s[i]; visited2[idx]=1; int l; int r; for (int j=idx-1;j>=0;j--){ if(visited2[j]==0) l=j; break; } for (int j=idx+1;j<=N+1;j++){ if(visited2[j]==0) r=j; break; } sum=sum+a[r]*a[l]; } sum+=2*getMax(); return sum; } void backtrack(int pos){ for (int i=1;i<=N;i++){ if(!visited[i]){ visited[i]=1; s[pos]=i; if(pos==N-2){ reset(); int value=tinh(0); if(value>res) res=value; } else backtrack(pos+1); visited[i]=0; } } } int main(){ freopen("input.txt","r",stdin); cin>>T; for (int t=1;t<=T;t++){ cin>>N; for (int i=1;i<=N;i++){ cin>>a[i]; } a[0]=1; a[N+1]=1; backtrack(1); cout<<res<<endl; } return 0; }
Editor is loading...
Leave a Comment