记忆化搜索

C++ 代码

#include <iostream>
using namespace std;

const int maxn = 30;
int a[maxn];
int f[maxn][maxn];  //f[i][j]表示区间[i, j]最大得分
int r[maxn][maxn];  //r[i][j]表示使区间[i, j]得分最大的根节点

long long dfs(int left, int right)
{
    if(left > right) return 1;
    if(f[left][right]) return f[left][right];
    long long maxv = 0;
    for(int i = left; i <= right; i ++)   //枚举区间[i, j]以i为根节点的情况，求最大得分
    {
        long long temp = dfs(left, i - 1) * dfs(i + 1, right) + a[i];
        if(temp > maxv)
        {
            maxv = temp;
            r[left][right] = i;
        }
    }
    return f[left][right] = maxv;
}

void dfs1(int left, int right)   //前序遍历
{
    if(left > right) return;
    cout << r[left][right] << " ";
    dfs1(left, r[left][right] - 1);
    dfs1(r[left][right] + 1, right);
}

int main()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; i ++)
        cin >> a[i];
    for(int i = 1; i <= n; i ++)
    {
        r[i][i] = i;
        f[i][i] = a[i];
    }
    cout << dfs(1, n) << endl;
    dfs1(1, n);
}