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[], root[][];
unsigned long long dp[][];
void print(int i, int j)
{
if (i == j)
cout << i << ' ';
else if (i < j)
{
cout << root[i][j] << ' ';
print(i, root[i][j] - );
print(root[i][j] + , j);
}
}
int main()
{
cin >> n;
for (int i = ; 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 = ; i <= n; i++)
dp[i][i] = num[i];
for (int len = ; len <= n; len++)
{
for (int i = , j = len; j <= n; i++, j++)
{
for (int k = i; k <= j; k++)
{
int multiple = ;
if (k != i)
multiple *= dp[i][k - ];
if (k != j)
multiple *= dp[k + ][j];
if (dp[i][j] < num[k] + multiple)
{
dp[i][j] = num[k] + multiple;
root[i][j] = k;
}
}
}
}
cout << dp[][n] << endl;
print(, n);
return ;
}