闫式dp分析
结果与初始化
中序遍历为w[1 ~ n]
的所有所有二叉树的最大得分,结果:f[1][n]
求最大得分,所以初始化为负无穷,这里负无穷使用0
来表示,当区间只有一个结点时,就只有根结点,所以f[i][i] = w[i]
细节处理
-
当根结点在左端点时,即 k = i
。f[i][k - 1]
是一个不合法状态,因为[i, k - 1]
所表示的区间右端点比左端点大。需要特殊处理。
-
当根结点在右端点时,即 k = j
。f[k + 1][j]
是一个不合法状态,因为[k + 1, j]
所表示的区间右端点比左端点大。需要特殊处理。
前序遍历
前序遍历的顺序时根、左、右,在计算最大得分的过程中,将每个区间对应的根结点记录,递归遍历区间时输出每个区间的根结点即可
迭代代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 35;
int f[N][N];
int w[N];
int root[N][N];
void dfs(int l, int r){
if(l > r) return;
int k = root[l][r];
printf("%d ", k);
dfs(l, k - 1);
dfs(k + 1, r);
}
int main(){
int n;
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;
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(i == j) score = w[k];
if(score > f[i][j])
{
f[i][j] = score;
root[i][j] = k;
}
}
}
printf("%d\n", f[1][n]);
dfs(1, n);
return 0;
}
记忆化搜索
为什么不能直接递归而是记忆化搜索

图中红色的区间是需要计算的区间,计算区间可能被区间1
、区间2
、区间3
划分出来,如果计算区间的结果没有被存储下来,那么计算区间就可能被重复计算,造成TLE
,所以需要存储计算过的区间,进行剪枝优化。
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 40;
int f[N][N];
int w[N];
int root[N][N];
int n;
int dfs(int l, int r){
if(l > r) return 1;
if(f[l][r] != -1) return f[l][r];
if(l == r){
f[l][r] = w[l];
root[l][r] = l;
return f[l][r];
}
for(int k = l; k <= r; k ++)
{
int left = dfs(l, k - 1);
int right = dfs(k + 1, r);
int score = left * right + w[k];
if(score > f[l][r])
{
f[l][r] = score;
root[l][r] = k;
}
}
return f[l][r];
}
void pre(int l, int r){
if(l > r) return ;
int k = root[l][r];
printf("%d ", k);
pre(l, k - 1);
pre(k + 1, r);
}
int main(){
cin >> n;
for(int i = 1; i <= n; i ++)
cin >> w[i];
memset(f, -1, sizeof f);
dfs(1, n);
printf("%d\n", f[1][n]);
pre(1, n);
return 0;
}