題目描述：
小Q和牛博士在玩一個石子合并的游戲，初始一共有n堆石子，每堆石子有w[i]個石子。小Q和牛博士他們需要對石子堆進行合并，每次他們可以任意選擇兩堆石子進行合并。一堆有x個石子的石子堆和一堆有y個石子的石子堆合并將得到一堆x+y個石子的石子堆，這次合并得分為x*y，當只剩下一堆石子的時候游戲結束。
小Q和牛博士希望采取優(yōu)秀的策略獲得最大得分，希望你能來幫他們算算最大得分多少。

image.png

image.png

思路：
可以發(fā)現(xiàn)不管合并的順序如何，結果都一致，所以以下代碼采用的是依次合并。
代碼：（C++）

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int a;
    vector<int> A(n);
    for(int i=0;i<n;i++)
    {
        cin>>a;
        A[i]=a;
    }
    int sum=0;
    for(int i=0;i<n-1;i++)
    {
        sum=sum+A[i]*A[i+1];
        A[i+1]=A[i]+A[i+1];
    }
    cout<<sum;
    return 0;
}

提交結果：

image.png