題目描述:
小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