编写题解 1255: 蓝桥杯算法提高-能量项链

解题思路:采取递归+深搜思想，将所有可能的结果都整一遍，选出最大值

注意事项:

参考代码:

#include<iostream>

#include<list>

#include<algorithm>

using namespace std;

struct beads//能量珠结构体

{

    int x;

    int y;

};

int dfs(beads a[],int n,int pre) {//能量珠数组 能量珠数 前面结合的能量珠释放的能量

    if (n == 1) { //

   //   cout << "pre: " << pre << endl;

        return pre;

    }

    int r = 0;

    for (int i = 0; i < n; i++) {

        int max1 = 0;

        max1 += a[i].x * a[i].y * a[(i + 1) % n].y + pre;//计算释放的能量

        beads* a1 = new beads[n - 1];//构建一个新数组存结合后的能量珠串

        a1[0].x = a[i].x;

        a1[0].y = a[(i + 1) % n].y;

        int pos = 1;

        int j = (i+2)%n;

        while (pos < n-1) {

            if (j != i && j != (i + 1) % n) {

                a1[pos].x = a[j].x;

                a1[pos++].y = a[j].y;

            }

            j = (j+1)%n;

        }

        max1 = dfs(a1, n - 1,max1);

        r = max(r, max1);

    }

    return r;

}

int main()

{

    int n;

    cin >> n;

    int* array = new int[n];

    for (int i = 0; i < n; i++) {

        cin >> array[i];

    }

    beads* a = new beads[n];

    for (int i = 0; i < n; i++) {

        a[i].x = array[i];

        a[i].y = array[(i + 1) % n];

    }

    //cout << "+++++++++++++++++++++++++++++++" << endl;

    cout << dfs(a, n,0);

    return 0;

}