腾讯 石子合并 博弈

题目描述

小Q和牛博士在玩一个石子合并的游戏,初始一共有n堆石子,每堆石子有w[i]个石子。小Q和牛博士他们需要对石子堆进行合并,每次他们可以任意选择两堆石子进行合并。一堆有x个石子的石子堆和一堆有y个石子的石子堆合并将得到一堆x+y个石子的石子堆,这次合并得分为x*y,当只剩下一堆石子的时候游戏结束。

、小Q和牛博士希望采取优秀的策略获得最大得分,希望你能来帮他们算算最大得分多少。

输入描述:

输入包括两行,第一行一个正整数n(2≤n≤100)。第二行包括n个正整数w[i](1≤w[i]≤100),即每堆石子的个数。

输出描述:

输出一个正整数,即小Q和牛博士最大得分是多少。

示例1

输入

3
1 2 3

输出

11
#include<iostream>
#include<algorithm>
#include<set>
using namespace std;
int main()
{
    int n;
    while(cin>>n)
    {
        int num;
        multiset<int> s;
        for(int i=0;i<n;++i)
        {
            cin>>num;
            s.insert(num);
        }
        int sum=0,a,b;
        while(s.size()!=1)
        {
            a=*s.begin();
            s.erase(s.begin());
            b=*s.begin();
            s.erase(s.begin());
            num=a+b;
            s.insert(num);
            sum+=a*b;
        }
        cout<<sum<<endl;
    }
    return 0;
}
Last modification:January 12th, 2020 at 12:56 am
如果觉得我的文章对你有用,请随意赞赏