时间限制 10000 ms 内存限制 64 MB
题目描述
刚刚今天去游乐场玩，发现了一个新的游戏项目，游戏是这样的，场上一共有 n 个气球，它们的编号是0到n-1，然后每个气球上还有一个数字，我们使用数组nums来保存这些数字。 现在游戏要求刚刚戳破所有的气球。每当刚刚戳破一个气球i时，刚刚可以获得nums[left] * nums[i] * nums[right]个积分。这里的left和right指的是和i相邻的两个气球的序号。（注意每当刚刚戳破了气球i后，气球left和气球right就变成了相邻的气球。） 求所能获得积分的最大值。
输入数据
输入中有若干组测试样例，第一行为一个正整数T(T≤1000)，表示测试样例组数。每组测试样例包含2部分： 第一部分有一行，包含1个正整数n（0≤n≤500），第二部分为一行，有n个数，第i个数表示num[i],(0≤num[i]≤100)。
输出数据
对每组测试数据，单独输出一行答案，表示最大的积分值
样例输入
1 4 3 1 5 8
样例输出
167
#define _CRT_SECURE_NO_WARNINGS #include <cstdio> #include <algorithm> #include <string> #include <iostream> using namespace std; int num[502] = { 0 }; int maxans = 0; int main() { int T; cin >> T; while (T--) { int n; cin >> n; for (int w = 0; w <= n + 2; w++) { num[w] = 1; } for (int i = 1; i <= n; i++) { cin >> num[i]; } if (n == 0) { continue; } if (n == 1) { cout << num[1] << endl; continue; } int ans[502][502] = { 0 }; for(int span = 1; span <= n; ++span){ for(int i = 1; i <= n - span + 1; ++i){ int j = i + span - 1; for(int k = i; k <= j; ++k){ ans[i][j] = max(ans[i][j], ans[i][k - 1] + ans[k + 1][j] + num[i - 1] * num[k] * num[j + 1]); } } } cout << ans[1][n] << endl; } return 0; }