2020 CCPC Wannafly Winter Camp Day6 Div.12——N.合并！【思维】

题目传送门

题目描述

有 ${n} 个石子堆，第 $i$ 个在一开始有 $a_i$ 个石子。每次你可以选择两堆相邻的石子 $a_i,a_{i+1}$ 合并，合并完之后得到的收益为$a_i{a}_{i+1}$，两堆石子变成一堆有 $a_i+a_j$ 个石子的堆。
你会一直进行合并操作，直到只剩下一堆石子为止。
求你能得到的最大的收益之和。

输入描述:

第一行一个正整数 $n$
第二行 $n$ 个正整数，表示 $a_{1...n}$
$1\le n,a_i\le 2000$

输出描述:

输出一个数，表示能获得的最大收益

输入

3
1 2 3

输出

11

题解

• 其实?论怎么进?合并，最后的答案?定是 $a[1\dots n]$ 两两的乘积之和

AC-Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;const int maxn = 2005;
int a[maxn];
int main() {
    int n;while (cin >> n) {
    for (int i = 1; i <= n; ++i) cin >> a[i];ll ans = 0;for(int i = 1; i <= n; ++i)for(int j = i+1; j <= n; ++j)ans += a[i]*a[j];cout << ans << endl;}
}