能量项链-题解

解题思路:

为了可以得到能量的最大值，最为简单的思路即为将最小的数字放在两数字的中间被吃掉，逐渐过滤掉最小的数字，最终得到能量总值便是最大值。

以样例输入为例子：

2 3 5 10

得到其中最小的数字为 2，要将它吃掉，先通过10 - 2 - 3的组合，将 2 这个数字吃掉。得到此时释放的能量为：10*2*3 = 60，数据形式变为：

0 3 5 10    （被吃掉的数用0替代）

得到其中除 0 以外的最小数字为 3，将它吃掉，通过10 - 3 - 5这样的组合即可。得到此时释放的能量为：10 * 3 * 5 = 150，数据形式变为：

0 0 5 10

同上述理，通过组合10 - 5 - 10的组合把 5 吃掉就可以了，释放能量 10 * 5 * 10 = 500，数据形式变为：

0 0 0 10

一共进行了 4 - 1 的讨论，类推出像这样形式的分析需要进行N-1次。

参考代码:

#include <stdio.h>

int main() {
    int n, An[200];
    scanf("%d", &n);

    for(int i = 0; i < n; i ++)
        scanf("%d", &An[i]);

    int TheMin = An[0], pos, sum = 0;

    for(int i = 0; i < n - 1; i ++){    //  进行 N - 1次讨论
        int TheRight, TheLeft, temp1, temp2;
        // pos用来标记最小值的所在位置不宜改动，使用两个临时变量 temp1, temp2 辅助向左向右寻找非零值
        for(int j = 0; j < n; j ++){
            if( !An[j] )
                continue;
            if(TheMin >= An[j]){
                pos = j;
                TheMin = An[j];
            }
        }   //  寻找数列中除了 0 以外的最小值

        temp1 = pos;
        for(int t = 1; t < n; t ++){
            if(temp1 + t == n)
                temp1 -= n;
            if( An[temp1 + t] != 0 )
                TheRight = An[temp1 + t];
        }   //  从最小值的标记位开始向右寻找除了 0 以外的值

        temp2 = pos;
        for(int t = 1; t < n; t ++){
            if(temp2 - t == -1)
                temp2 += n;
            if( An[temp2 - t] != 0 )
                TheLeft = An[temp2 - t];
        }   //  从最小值的标记位开始向左寻找除了 0 以外的值

        sum += TheLeft * TheMin * TheRight; //  得到该次分析所释放的能量

        TheMin = TheLeft;
        An[pos] = 0;                        //  将变量初始化
    }
    printf("%d", sum);
    return 0;
}

若有改进，欢迎与我讨论٩(˃̶͈̀௰˂̶͈́)و