C++重中之重来喽！6.6 递归结构问题 (1) 乘积最大(2) 加分二叉树（有分析，有答案）【推荐收藏】

【问题简述】在一个长度为 n 的非 0 数字串中插入 k 个乘号，使表达式的值最大。（6≤n≤40，1≤k≤6）
【分析】
1. 划分阶段：以一个乘号为一个阶段。
2. 状态表示：f(i,l)表示前 i 个数字插入 l 个乘号之后的最大乘积。

3. 状态转移方程：f(i,l) = max{f(j, l－1)×s(j＋1, n)}，l 边界条件：f(i,0) = s(1,i)
其中 s(a,b)表示连接第 a 个数字到第 b 个数字之后表示的整数。

#include 
#include 
using namespace std;
struct hp {……}; // 见123页“11.7 高精度算法（压位存储）!”。
int n, k;
hp f[51][21], s[51][51];
int main()
{
char c;
long long t;
cin>>n>>k;
memset(f,0,sizeof(f)); memset(s,0,sizeof(s));
for (int i=1;i<=n;i++)
{
cin>>c;
s[i][i]=c-'0';
t=1;
for (int j=i-1;j>0;j--)
s[j][i]=s[j][j]*(t*=10)+s[j+1][i]; // 递推计算s
f[i][0]=s[1][i];
}
for (int i=1;i<=n;i++)
for (int l=1; l<=min(i-1, k); l++)
{
f[i][l] = 0;
for (int j=l;j 
(2) 加分二叉树 
【问题简述】设一个 n 个结点的二叉树的中序遍历为（1,2,3,…,n），其中数字 1,2,3,…,n 为结点编号。每个结点都有一个分数（均为正整数），记第 i 个结点的分数为 di，二叉树及它的每个子树都有一个加分，任一棵子树（也包含二叉树本身）的加分＝左子树的加分×右子树的加分＋根的分数若某个子树为主，规定其加分为 1，叶子的加分就是叶结点本身的分数。不考虑它的空子树。求一棵符合中序遍历为（1,2,3,…,n）且加分最高的二叉树。要求输出最高加分和前序遍历。
 
 【分析】
 本题中的树是无根树，需要枚举节点作为根的情况，重复有根树的动态规划过程。
 1. 状态表示：f(i,j)表示由第 i 个元素到第 j 个元素组成的二叉树的最大加分。
 2. 状态转移方程：f(i,j) = max{f(i,k－1)×f(k＋1,j)＋dk}，i≤k≤j（实际上，这里的 k 表示根结点）
    边界条件：f(i,i) = di
 3. 递推时注意，循环的最外层不是 i，也不是 j，而是 j－i！
 
#include 
#include 
using namespace std;
int n, root[31][31];
unsigned int f[31][31], d[31];
void preorder(int i, int j) // 按前序遍历输出最大加分二叉树
{
int k=root[i][j];
if (k==0) return;
cout<>n;
for (int i=1; i<=n; i++) cin>>d[i];
for (int i=0; i<=n; i++) // 计算单个结点构成的二叉树的加分，并记录根结点
{
f[i][i]=d[i];
root[i][i]=i;
f[i+1][i]=1;
}
for (int p=1; p f[i][j]) f[i][j] = temp, root[i][j] = k;
}
}
cout<