递归结构问题

发表于 2024-1-2 17:31:48

(1) 乘积最大

【问题简述】在一个长度为 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<j<i, l≤min{k, i－1} 边界条件：f(i,0) = s(1,i)

其中 s(a,b)表示连接第 a 个数字到第 b 个数字之后表示的整数。

#include <iostream> #include <cstring> 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=c-'0';

t=1;

for (int j=i-1;j>0;j--) s[j]=s[j][j]*(t*=10)+s[j+1]; // 递推计算s

f[0]=s[1];

}

for (int i=1;i<=n;i++) for (int l=1; l<=min(i-1, k); l++)

{

f[l] = 0;

for (int j=l;j<i;j++) f[l] = max(f[l], f[j][l-1]*s[j+1]);

}

cout<<f[n][k]<<endl; return 0;

}

(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 <iostream> #include <cstring> using namespace std;

int n, root[31][31]; unsigned int f[31][31], d[31];

void preorder(int i, int j) // 按前序遍历输出最大加分二叉树

{ int k=root[j]; if (k==0) return;

cout<<k<<" "; preorder(i, k-1); preorder(k+1, j);

} int main()

{ memset(root, 0, sizeof(root)); memset(f, 0, sizeof(f)); memset(d, 0, sizeof(d));

cin>>n;

for (int i=1; i<=n; i++) cin>>d;

for (int i=0; i<=n; i++) // 计算单个结点构成的二叉树的加分，并记录根结点

{

f=d; root=i; f[i+1]=1;

}

for (int p=1; p<n; p++) // 依次计算间距为d的两个结点构成的二叉树的最大加分 for (int i=1; i<=n-p; i++)

{

int j=i+p;

for (int k=i; k<=j; k++)

{

int temp = f[k-1] * f[k+1][j] + d[k]; if (temp > f[j]) f[j] = temp, root[j] = k;

}

cout<<f[1][n]<<endl; preorder(1, n); return 0;

}