題目描述：
小Q和牛博士在玩一個(gè)石子合并的游戲，初始一共有n堆石子耍休，每堆石子有w[i]個(gè)石子谋右。小Q和牛博士他們需要對(duì)石子堆進(jìn)行合并灶泵，每次他們可以任意選擇兩堆石子進(jìn)行合并育八。一堆有x個(gè)石子的石子堆和一堆有y個(gè)石子的石子堆合并將得到一堆x+y個(gè)石子的石子堆，這次合并得分為x*y赦邻，當(dāng)只剩下一堆石子的時(shí)候游戲結(jié)束髓棋。
小Q和牛博士希望采取優(yōu)秀的策略獲得最大得分，希望你能來幫他們算算最大得分多少惶洲。
image.png
image.png
思路：
可以發(fā)現(xiàn)不管合并的順序如何按声，結(jié)果都一致，所以以下代碼采用的是依次合并恬吕。
代碼：（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;
}
提交結(jié)果：
image.png
