Description

给定 8 个数，如果将它们排成一列，每个数的权值是它与相邻的数之积，求一个排列方式，所有数的权值之和最大，输出该权值和.

例如 13242315 的权值和为 1∗3+3∗1∗2+2∗3∗4+4∗2∗2+2∗4∗3+3∗2∗1+1∗3∗5+5∗1=99

Input

每组数据一行 8 个空格隔开的数 1≤��≤100.

Output

求最大的权值和.

Sample

#0

Input

Copy

1 3 2 4 2 3 1 5
3 5 6 8 7 1 2 6
1 2 3 4 5 6 7 8
23 99 63 67 20 64 44 51

Output

Copy

190
1129
987
1483816

回溯法秒了

#include<iostream>
#include<cmath>
#include"stdio.h"
#include "string"
using namespace std;
#include "cstring"
#include "vector"
#include "algorithm"
void calAns(vector<int>&path,int &Max){
    int max_temp=0;
    for(int i=0;i<8;i++){
        if(i==0){
            max_temp+=path[0]*path[1];
        }
        else if(i==7){
            max_temp+=path[7]*path[6];
        }
        else{
            max_temp+=path[i]*path[i-1]*path[i+1];
        }
    }
//    cout<<"max="<<max_temp<<endl;
    Max=max(max_temp,Max);
}
void backtrack(int a[],int startIndex,vector<int>&path,vector<int>&contain,int &Max){
    if(path.size()==8){
        calAns(path,Max);
        return;
    }
    for(int i=0;i<8;i++){
        if(find(contain.begin(), contain.end(),i)==contain.end()){
            path.push_back(a[i]);
            contain.push_back(i);
            backtrack(a,startIndex+1,path,contain,Max);
            path.pop_back();
            contain.pop_back();
        }
    }
}
int b[10];
int main()
{
    while(cin>>b[0]){
        for(int i=1;i<8;i++){
            cin>>b[i];
        }
        int Max=0;
        vector<int>path,contain;
        backtrack(b,0,path,contain,Max);
        cout<<Max<<endl;
    }

    return 0;
}