本文主要是介绍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）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
