P1040 加分二叉树(区间DP)
2024-08-30 14:39:19
解题思路
题目已经给出了树的中序遍历,因此我的想法是利用中序遍历的特点:若某子树的根结点为k,那么k之前的结点组成这一子树的左子树,k之后的结点组成这一子树的右子树,可以通过不断地枚举每个子树的根结点k,求出每个子树的最大加分:{ 左子树的最大加分*右子树的最大加分+ 根结点k的值}
以上是通过已知中序遍历想到是方法,结合已知条件,对于某一子树的中序遍历: {l, l + 1, ... , r} ,若根节点为k,那么 {l, l +1,...,k-1} 即为这一子树的左子树,{k+1,k+2,...,r}即为这一子树的右子树,因此,可以通过这种方法构造所有可能的树结构
根据上面的方法,我们通过递归求出每一段中序遍历{l,l+1,...,r}代表的子树的最大加分dp[l][r]以及根结点root[l][r],根据状态转移方程
dp[l][r] = max(dp[l][r],dp[l][k-1] + dp[k+1][r] + val[k]) { l <= k <= r}
并记录dp[l][r]取最大值时的根结点root[l][r],这样一来dp[1][n]即为我们所求的最大加分,又利用root和中序遍历求出前序遍历
代码区
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<string>
#include<fstream>
#include<vector>
#include<stack>
#include <map>
#include <iomanip> #define bug cout << "**********" << endl
#define show(x, y) cout<<"["<<x<<","<<y<<"] "
#define LOCAL = 1;
using namespace std;
typedef long long ll;
const ll inf = 1e18 + ;
const int mod = 1e9 + ;
const int Max = 1e5 + ; int n;
ll val[];
ll dp[][]; //表示[l,r]子树的最大加分
int root[][]; //表示[l,r]子树的根结点
//dp,root均为以[l,r]组成的子树的数据 ll dfs(int l, int r)
{
if (l > r) //空树
return ;
if(l == r) //叶子节点
return dp[l][r] = val[l]; if (dp[l][r] != -)
{
return dp[l][r];
} for (int k = l; k <= r; k++) //枚举子树[l,r]的根结点
{
ll now = dfs(l,k-) * dfs(k + , r) + val[k];
if(now > dp[l][r])
dp[l][r] = now,root[l][r] = k;
}
return dp[l][r];
} void dfs2(int l,int r)
{
if(l > r) //空树
return;
printf("%d ",root[l][r]);
dfs2(l,root[l][r] - );
dfs2(root[l][r] + , r);
} int main()
{
#ifdef LOCAL
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
scanf("%d", &n);
for (int i = ; i <= n; i++)
scanf("%lld", val + i),root[i][i] = i; memset(dp,-,sizeof(dp));
dfs(,n); printf("%lld\n",dp[][n]);
dfs2(,n);
printf("\n");
return ;
}
最新文章
- 执行后台任务的利器&mdash;&mdash;Hangfire
- css3 缓动公式
- 开始使用DOJO(翻译)
- linux(ubuntu)安装时遇到的问题
- SAP ST03N工作负载的后台作业定义
- Filter过滤非法字符
- Android(java)学习笔记128:使用proguard混淆android代码
- 捉虫记:SHGetSpecialFolderPath返回错误码为2
- OSX10.11 CocoaPods 升级总结
- 《Programming WPF》翻译 第6章 5.我们进行到哪里了?
- 美版nexus 5 LG D820才支持CDMA,国际版LG D821不支持
- 360路由器设置网段ip
- GC机制总结
- Safari无痕模式是不能只使用localStorage存储数据要用Cookie做补丁
- iptables(4)规则编写
- mysql时间延时注入案例
- SQL row_number() over(partition by函数
- Lemon OA第2篇:功能解析方法
- who am i ?
- Codeforces Beta Round #11 B. Jumping Jack 数学