NC214360. 石子合并
描述
牛牛有 n 堆石子， 每堆石子有 a[i] 个， 牛牛每次可以选择相邻的两堆石子，然后拿走少的那一堆，得到的价值是两堆石子个数之和， 直到只剩下一堆石子。
如果拿走了第 i 堆石子， 那么第 i-1 堆和第 i+1 堆 就会相邻。
牛牛想知道该怎么拿，才能使得到的价值最多。
输入描述
第一行一个整数 n， 1 ≤ n ≤ 2e5第二行 n 个整数 a[i]，0 ≤ a [i] ≤ 1e9
输出描述
输出得到的最大价值
示例1
输入:
5 2 5 3 5 1
输出:
31
C++(clang++11) 解法, 执行用时: 67ms, 内存消耗: 400K, 提交时间: 2020-12-05 19:05:02
#include<iostream>
using namespace std;
int main()
{
long long n,m=-1,s=0;
cin>>n;
for(int i=0;i<n;i++)
{
long long x;
cin>>x;
m=max(x,m);
s+=x;
}
cout<<s+m*(n-2);
}
pypy3 解法, 执行用时: 238ms, 内存消耗: 42780K, 提交时间: 2022-03-28 16:40:35
input() a = list(map(int, input().split())) print(sum(a) + (len(a) - 2) * max(a))
Python3(3.9) 解法, 执行用时: 73ms, 内存消耗: 26528K, 提交时间: 2021-02-23 13:02:00
n=int(input()) l=list(map(int,input().split())) print(max(l)*(n-2)+sum(l))