【CSU-1980】解题报告（区间dp，树的中序遍历）

原始题目

1980: 不堪重负的树

  • Time Limit: 1 Sec
  • Memory Limit: 128 Mb
  • Submitted: 188
  • Solved: 83

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

题目大意

如题 # 解题思路 - 先求得中序遍历各节点的权值 - 预处理前缀和，以及dp数组（初始\(dp[i][i]=f[i]\)） - 对于一棵树可以由左子树、右子树的最优解转移过来，区间dp - 状态转移方程 \[dp[i][j]=min(dp[i][k-1]+dp[k+1][j])+\sum_{m=i}^{j} f[i] (i<k<j)\] - 注意边界情况（某子树为空时）

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
//#include <bits/stdc++.h>
#define ms(i,a) memset((i),(a),sizeof(i))
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define np next_permutation
#define all(x) x.begin(),x.end()
#define fi first
#define se second
#define SZ(x) ((ll)(x).size()) 
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
const ll maxn=200+5;
ll dp[maxn][maxn],p[maxn],w[maxn],f[maxn],sum[maxn];
ll n,t;
void initial(){
	rep(i,1,n+1){
		f[i]=w[p[i]];
	} 
	rep(i,1,n+1){
		rep(j,i,n+1){
			if(i==j) dp[i][j]=f[i];
			else dp[i][j]=INF; 
		}
	}
	sum[0]=0;
    rep(i,1,n+1) sum[i]=sum[i-1]+f[i];//前缀和 
} 
int main()
{
	ios::sync_with_stdio(false); 
    cin>>t;
    while(t--)
    {
        cin>>n;
        rep(i,1,n+1)cin>>w[i];
        rep(i,1,n+1)cin>>p[i];
        initial(); 
        
        for(ll len=2;len<=n;len++){
        	for(ll i=1;i+len-1<=n;i++){
        		ll j=i+len-1;
        		dp[i][j]=min(dp[i+1][j],dp[i][j-1])+sum[j]-sum[i-1];
        		for(ll k=i+1;k<j;k++){
        			dp[i][j]=min(dp[i][j],dp[i][k-1]+dp[k+1][j]+sum[j]-sum[i-1]);
				}
        		
			}
		}
        cout<<dp[1][n]<<endl;
    }
    return 0;
}

收获与反思

  • 区间DP逐渐形成自己的写法
  • 注意边界条件的考虑，这里需要考虑空树的情况， \[dp[i][j]=min(dp[i+1][j],dp[i][j-1])+sum[j]-sum[i-1]\]