虽然代码AC了,但是还有些地方不是很理解
int left = k == i ? 1 : f[i][k-1];
这一步表示:当决策点是区间最左侧的值时,为什么就表示叶子结点呢?有知道的大佬请打在评论区…^-^
#include<bits/stdc++.h>
using namespace std;
const int N = 35;
int w[N],f[N][N],g[N][N]; //g是决策点
int n;
void dfs(int l,int r)
{
if(l>r) return;
int k = g[l][r];
cout<<g[l][r]<<' ';
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++)
{
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;
else
{
for(int k=i;k<=j;k++) //
{
int left = k == i ? 1 : f[i][k-1];
int right = k ==j ? 1 : f[k+1][j];
int score = left * right + w[k]; //
if(score>f[i][j])
{
f[i][j]=score;
g[i][j]=k;
}
}
}
}
}
cout<<f[1][n]<<endl;
dfs(1,n);
}
k
为根节点,k == l
时,表示没有左儿子,空默认为 $1$