【NOIP2003提高组】加分二叉树

https://www.luogu.org/problem/show?pid=1040

令f(i,j)表示[i,j]的二叉树中最高的分数。
枚举k为根，状转方程：f(i,j)=max{f(i,k-1)*f(k+1,j)+num[k]} (i<=k<=j)
做决策的时候保存最优解的根，然后模拟前序遍历递归打印。

#include <iostream>
using namespace std;
int n, num[40], root[40][40];
unsigned long long dp[40][40];
void print(int i, int j)
{
    if (i == j)
        cout << i << ' ';
    else if (i < j)
    {
        cout << root[i][j] << ' ';
        print(i, root[i][j] - 1);
        print(root[i][j] + 1, j);
    }
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> num[i];
    // f(i,j)=max{f(i,k-1)*f(k+1,j)+num[k]} (i<=k<=j)
    for (int i = 1; i <= n; i++)
        dp[i][i] = num[i];
    for (int len = 2; len <= n; len++)
    {
        for (int i = 1, j = len; j <= n; i++, j++)
        {
            for (int k = i; k <= j; k++)
            {
                int multiple = 1;
                if (k != i)
                    multiple *= dp[i][k - 1];
                if (k != j)
                    multiple *= dp[k + 1][j];
                if (dp[i][j] < num[k] + multiple)
                {
                    dp[i][j] = num[k] + multiple;
                    root[i][j] = k;
                }
            }
        }
    }
    cout << dp[1][n] << endl;
    print(1, n);
    return 0;
}