注意题意指出特判,左子树为空时 权值 = w + B;右子树为空, w + A; 左右均空 权值 w;
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 35;
int n;
int w[N], f[N][N], g[N][N]; //权值,状态表示(数组),决策点(取到最优解的具体子集)。
void dfs(int l, int r) //每次输出(l, r)区间内的前序遍历
{
if (l > r) return; //子树为空,不用输出直接返回
int k = g[l][r]; //求当前子树的根节点
cout << k << ' '; //输出根节点
dfs(l, k - 1), dfs(k + 1, r); //输出左子树,输出右子树
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i++) cin >> w[i]; //每个序列每个点的权值
for (int len = 1; len <= n; len++) //区间DP模板:①枚举长度
for (int i = 1; i + len - 1 <= n; i++)//②左端点
{
int j = i + len - 1; //右端点
if (len == 1) f[i][j] = w[i], g[i][j] = i; //特判长度为一时,状态即为w[自己],决策点即为自己 。ps.:自己=i即当前
else
{
for (int k = i; k <= j; k++)//枚举决策点
{
int left = k == i ? 1 : f[i][k - 1]; //左子树权值.边界k时则为1,否则f[i, k - 1]
int right = k == j ? 1 : f[k + 1][j]; //右子树权值.边界k时则为1,否则f[k + 1, j]
int score = left * right + w[k];//分值等于
if (score > f[i][j])
{
f[i][j] = score;//分值更大时,更新状态
g[i][j] = k; //决策点 = k
}
}
}
}
cout << f[1][n] << endl; //全局最优解
dfs(1, n); //输出方案。
return 0;
}