A18502. 消消乐
填空题
困难
知识点
题目描述
消消乐
题目描述
给定一个由 n 个整数构成的数组 a = [a1,.....,an]。每次你可以对数组 a 进行以下操作，直到数组 a 变为空：
- 指定 a 中的一个元素，获得该元素两侧相邻元素之和的分数，并将该元素从 a 中删去。
特别地，如果相邻元素不存在则该元素的值视为 0。例如，对于 a = [1,2,3] 可以进行以下操作：
- 指定元素 2，获得分数 1+3，删去 2 后 a = [1,3]；
- 指定元素 1，获得分数 0+3，删去 1 后 a = [3]；
- 指定元素 3，获得分数 0+0，删去 3 后 a 变为空。
请问你能获得的分数总和最大是多少？
输入格式
第一行，一个正整数 n，表示数组长度。
第二行，n 个非负整数 a1,.....,an，表示数组 a 中的整数。
输出格式
输出一行，一个整数，表示能获得的最大分数总和。
输入样例 1
6
1 6 3 2 9 1输出样例 1
55输入样例 2
5
3 1415 926 53 58输出样例 2
5771参考答案
#include <iostream>
#include <algorithm>
using namespace std;
int n;
int a[110];
long long f[110][110];
int main() {
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= n; i++)
for (int l = 1, r = i; r <= n; l++, r++)
for (int k = l; k <= r; k++)
f[l][r] = max(f[l][r], f[l][k - 1] + f[k + 1][r] + a[l - 1] + a[r + 1]);
cout << f[1][n] << endl;
return 0;
}
上一题
下一题