考察:区间DP+dfs
关键在于想出怎么区间DP
思路:
根据石子合并那道题,f[l,r]是要合并的石子区间,那么这道题的f[l,r]是(l,r)区间内形成的二叉树,石子区间那道题集合的划分是根据隔板k的位置,那么这道题就是根节点的位置.要注意特殊的结点:
- 叶子结点,我们需要初始化叶子节点,即f[i][i]=s[i].
- 左右子树存在一方为空的点.因为叶子结点已经占了f[i][i],所以只能特判是否左子树或右子树为空.
dfs:需要用数组记录[l,r]区间内的根.dfs遍历[1,n]的根节点.因为是先序遍历,所以我们找到根就立即输出.
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 const int N = 50; 7 int f[N][N],s[N],g[N][N]; 8 void dfs(int l,int r) 9 { 10 if(!g[l][r]) return; 11 int val = g[l][r]; 12 printf("%d ",val); 13 dfs(l,val-1); 14 dfs(val+1,r); 15 } 16 int main() 17 { 18 int n; 19 scanf("%d",&n); 20 for(int i=1;i<=n;i++) scanf("%d",&s[i]); 21 for(int len=1;len<=n;len++) 22 for(int l=1;l+len-1<=n;l++) 23 { 24 int r = l+len-1; 25 for(int k=l;k<=r;k++) 26 { 27 int lef = k==l?1:f[l][k-1];//如果根是最左,那么左子树=1 28 int rig = k==r?1:f[k+1][r];//根是最右 29 int score = lef*rig+s[k]; 30 if(l==r) score = s[k];//叶子结点的特点,左右根相等 31 if(score>f[l][r]) f[l][r] = score,g[l][r] = k; 32 } 33 } 34 printf("%d\n",f[1][n]); 35 dfs(1,n); 36 return 0; 37 }