CSU 1980: 不堪重负的树(区间DP)

2023-11-24 07:10
文章标签 dp 区间 csu 1980 不堪重负

本文主要是介绍CSU 1980: 不堪重负的树(区间DP),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

CSU1980

Description

小X非常喜欢树,然后他生成了一个大森林给自己玩。
玩着玩着,小X陷入了沉思。

  • 一棵树由N个节点组成,编号为i的节点有一个价值Wi。
  • 假设从树根出发前往第i个节点(可能是树根自己),一共需要经过Di个节点(包括起点和终点),那么这个节点对这棵树产生的负担就是Di与Wi的乘积。
  • 对于一棵树而言,这棵树的负担值为所有节点对它产生的负担之和。

小X学习了dfs,如果他知道树的结构,他当然可以很容易地算出树的负担值。可是现在沉思中的小X并不知道树的结构形态,他只知道一棵二叉树的中序遍历以及每个节点的价值,那么这棵二叉树可能的最小负担值是多少呢?

Input

第一行为一个正整数T(T≤20)表示数据组数。
每组数据包括三行。
第一行为一个正整数N(N≤200)。
第二行为N个正整数Wi(Wi≤108),表示编号为i的节点的价值。
第三行为N个正整数Pi(Pi≤N),为一个1~N的排列,表示二叉树的中序遍历结果。

Output

对于每组数据,输出一行一个正整数,表示这棵树可能的最小负担值。

Sample Input

2
4
1 2 3 4
1 2 3 4
7
1 1 1 1 1 1 1
4 2 3 5 7 1 6

Sample Output

18
17

Hint

对于第一个样例,树根为3,3的左儿子是2,3的右儿子是4,2的左儿子是1,这样构成的树可以达到最小负担。
对于第二个样例,对应的满二叉树可以达到最小负担。

Source

2017年8月月赛

Author

devember

题意:

给出一颗二叉树的中序遍历以及每一个节点的价值,给出负担值的计算公式,求一棵最小负担值的树。其中,根节点的负担就是自身的价值。

分析:

理解这道题,先得从输入数据开始:

第一行T表示数据组数;第二行N代表树的节点数;第三行N个整数Wi,代表编号为i的节点的价值;第四行N个整数Pi,表示中序遍历的结果。

(特别注意:这里的pi和wi不是一一对应的!!!)

首先让我们回顾一下中序遍历的概念:

图片来自网络

1 前序遍历:先遍历根结点,然后遍历左子树,最后遍历右子树。

 ABDHECFG

2.中序遍历:先遍历左子树,然后遍历根结点,最后遍历右子树。

HDBEAFCG

3.后序遍历:先遍历左子树,然后遍历右子树,最后遍历根节点。

HDEBFGCA

了解中序遍历的概念之后,我们就可以想到,根据输入的中序遍历结果。只要确定根节点,也就意味着将这棵树分成了左子树和右子树!

根据根节点做区间划分,能将问题分解成为两两合并的形式,本题的实质其实是一道区间dp的题目。

假设设置一个区间[i,j],i,j即为这棵树的最左最右节点。定义dp[i][j]为这个区间的最小负担值。由题意可得,dp[i][i]为该节点自身的价值。而其他区间的dp值都设置为未确定状态,由于本题求最小值,可以全部定义为INF(0x3f3f3f3f)。

根据上面的分析,即可得出状态转移方程:

dp[i][j] = min(dp[i][k-1] + dp[k+1][j]) + Value(i->j)

K为选取的根节点.因为现在多了一个根,那么它们到根的距离也就都多了1,根据题目对负担值的定义,需要加上value(i->j),即为该区间节点的总价值。

分析到这里,这道题目就变得很简单了,不过有几点必须要注意:
1.这道题数据得用long long;
2.由于pi和wi不是一一对应的,可以另开一个数组f存储正确的对应关系;
3.区间的价值可以先预处理求得前缀和,用一个数组s存储。

AC代码

#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<stack>
#define INF 0x3f3f3f3f
#define M 205
using namespace std;
long long dp[M][M],p[M],w[M],f[M],s[M];
int n,t;
int main()
{cin>>t;while(t--){cin>>n;for(int i=1;i<=n;i++)cin>>w[i];for(int i=1;i<=n;i++)cin>>p[i];for(int i=1;i<=n;i++)f[i]=w[p[i]];//对应关系 for(int i=1;i<=n;i++)s[i]=s[i-1]+f[i];//前缀和 for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++)dp[i][j]=INF;for(int i=1;i<=n;i++)dp[i][i]=f[i];for(int l=2;l<=n;l++)//第一维:长度 for(int i=1;i+l-1<=n;i++)//第二维:起始点 {int j=i+l-1;dp[i][j]=min(dp[i+1][j],dp[i][j-1])+s[j]-s[i-1];for(int k=i+1;k<j;k++)//第三维:中间点 dp[i][j]=min(dp[i][j],dp[i][k-1]+dp[k+1][j]+s[j]-s[i-1]);//状态转移方程 }cout<<dp[1][n]<<endl;}return 0;
}
/**********************************************************************Problem: 1980User: txhts1606Language: C++Result: ACTime:156 msMemory:2352 kb
**********************************************************************/

这篇关于CSU 1980: 不堪重负的树(区间DP)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/421494

相关文章

csu(背包的变形题)

题目链接 这是一道背包的变形题目。好题呀 题意:给n个怪物,m个人,每个人的魔法消耗和魔法伤害不同,求打死所有怪物所需的魔法 #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>//#include<u>#include<map

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

hdu4826(三维DP)

这是一个百度之星的资格赛第四题 题目链接:http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1004&cid=500 题意:从左上角的点到右上角的点,每个点只能走一遍,走的方向有三个:向上,向下,向右,求最大值。 咋一看像搜索题,先暴搜,TLE,然后剪枝,还是TLE.然后我就改方法,用DP来做,这题和普通dp相比,多个个向上

hdu1011(背包树形DP)

没有完全理解这题, m个人,攻打一个map,map的入口是1,在攻打某个结点之前要先攻打其他一个结点 dp[i][j]表示m个人攻打以第i个结点为根节点的子树得到的最优解 状态转移dp[i][ j ] = max(dp[i][j], dp[i][k]+dp[t][j-k]),其中t是i结点的子节点 代码如下: #include<iostream>#include<algorithm

hdu4865(概率DP)

题意:已知前一天和今天的天气概率,某天的天气概率和叶子的潮湿程度的概率,n天叶子的湿度,求n天最有可能的天气情况。 思路:概率DP,dp[i][j]表示第i天天气为j的概率,状态转移如下:dp[i][j] = max(dp[i][j, dp[i-1][k]*table2[k][j]*table1[j][col] )  代码如下: #include <stdio.h>#include

usaco 1.1 Broken Necklace(DP)

直接上代码 接触的第一道dp ps.大概的思路就是 先从左往右用一个数组在每个点记下蓝或黑的个数 再从右到左算一遍 最后取出最大的即可 核心语句在于: 如果 str[i] = 'r'  ,   rl[i]=rl[i-1]+1, bl[i]=0 如果 str[i] = 'b' ,  bl[i]=bl[i-1]+1, rl[i]=0 如果 str[i] = 'w',  bl[i]=b

hdu 1754 I Hate It(线段树,单点更新,区间最值)

题意是求一个线段中的最大数。 线段树的模板题,试用了一下交大的模板。效率有点略低。 代码: #include <stdio.h>#include <string.h>#define TREE_SIZE (1 << (20))//const int TREE_SIZE = 200000 + 10;int max(int a, int b){return a > b ? a :

uva 10154 DP 叠乌龟

题意: 给你几只乌龟,每只乌龟有自身的重量和力量。 每只乌龟的力量可以承受自身体重和在其上的几只乌龟的体重和内。 问最多能叠放几只乌龟。 解析: 先将乌龟按力量从小到大排列。 然后dp的时候从前往后叠,状态转移方程: dp[i][j] = dp[i - 1][j];if (dp[i - 1][j - 1] != inf && dp[i - 1][j - 1] <= t[i]

uva 10118 dP

题意: 给4列篮子,每次从某一列开始无放回拿蜡烛放入篮子里,并且篮子最多只能放5支蜡烛,数字代表蜡烛的颜色。 当拿出当前颜色的蜡烛在篮子里存在时,猪脚可以把蜡烛带回家。 问最多拿多少只蜡烛。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cs

uva 10069 DP + 大数加法

代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vector>#include <queue>#include <map>#include <cl