分治算法实践6-气球游戏 戳气球 C++_刚刚今天去游乐场玩,发现了一个新的游戏项目,游戏是这样的,场上一共有 n 个气球,

题目描述

刚刚今天去游乐场玩，发现了一个新的游戏项目，游戏是这样的，场上一共有 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
1
2
3

样例输出

167
1

解题思想

• emmm虽然把这道题放在分治里，但有很大部分是动态规划的事儿
• 维护一个数组rec[i][j] 记录 击中[i][j] 位置的最大总得分
• 二分法不断遍历，更新数组rec的记录信息
• 还有一个记录每个气球值的数组，这里要对这个数组进行处理的：因为要对当前气球值及其两侧的 做乘法，所以为了保证第一个气球和最后一个气球做乘法时，不出现数组越界的错误，要加一头一尾，值为1。

代码

#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;

int rec[502][502]; //rec[i][j]记录 击中[i][j] 位置的最大总得分
int val[502];      //记录每个点的值

int slove(int left, int right) //二分思想
{
    if (left >= right - 1)
        return 0;
    if (rec[left][right] != -1) //已经计算过当前位置的值，直接返回数组里存的数
        return rec[left][right];
    for (int i = left + 1; i < right; i++) //遍历
    {
        int sum = val[left] * val[i] * val[right];      //击中当前节点的得分
        sum = slove(left, i) + sum + slove(i, right);   //击中当前节点的总得分
        rec[left][right] = fmax(rec[left][right], sum); //不断更新 rec的值 取最大
    }
    return rec[left][right];
}
int max_score(int *num, int numSize)
{
    memset(rec, -1, sizeof(rec));
    val[0] = val[numSize + 1] = 1; //头 和 尾 要置1 （因为要做乘法)
    for (int i = 1; i <= numSize; i++)
    {
        val[i] = num[i - 1]; //更新val的值
    }
    //以上 数据准备
    int re = slove(0, numSize + 1); //记得+1 因为val“扩容”了
    return re;
}
int main()
{
    int T;
    cin >> T;
    int i, re, n;
    while (T--)
    {
        cin >> n;
        int num[n];
        for (int i = 0; i < n; i++)
            cin >> num[i];
        int re = max_score(num, n); //计算最大值
        cout << re;
    }
    system("pause");
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

写在最后：
leetcode上有类似题目：312-戳气球
若文章存在问题，还请各位大佬批评指正，共同进步。