CSU-1980 不堪重负的树

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，这样构成的树可以达到最小负担。

对于第二个样例，对应的满二叉树可以达到最小负担。

题解

首先我们要了解中序遍历，首先仅根据中序遍历是无法确定一颗树的，如果选定一个节点作为根节点，那么这个点左侧序列的点即为该节点的左子树，右边为右子树。这样我们很容易想到这个题可以区间DP

按区间长度从小到大枚举左右端点，枚举中间点做根，因为当一棵树成为一个点的子树时，就会增加子树节点价值和的负担值，所以对于l和r区间，如果l...(k - 1)成为第k个点的左子树，(k + 1)...r成为第k个点的右子树，那么就会增加\(pre[r] - pre[l]\)的负担值(pre为按照序列顺序的前缀和)，加上原先两棵子树的负担值，所以转移方程为

\[dp[l][r] = min(dp[l][k - 1] + dp[k + 1][r] + pre[r] - pre[l - 1], dp[l][r])
\]

初始化\(dp[i][i]\)为序列上第i个数对应的节点的权值,其他均为最大值

注意细节，如果一开始将\(dp[i][j]\)全部赋为inf，那么转移时注意判断中间点是区间左右端点的情况，否则左右端点的情况答案会为inf，因此WA了一发

#include<bits/stdc++.h>

#define maxn 250

using namespace std;

long long w[maxn];

int a[maxn];

long long f[maxn][maxn];

long long pre[maxn];

int main() {

	int t;

	scanf("%d", &t);

	while (t--) {

		int n;

		scanf("%d", &n);

		for (int i = 1; i <= n; i++) {

			scanf("%lld", &w[i]);

		}

		for (int i = 1; i <= n; i++) {

			scanf("%d", &a[i]);

		}

		for (int i = 1; i <= n; i++) {

			for (int j = 1; j <= n; j++) {

				f[i][j] = 0x7fffffffffffffff;

			}

		}

		for (int i = 1; i <= n; i++) {

			pre[i] = pre[i - 1] + w[a[i]];

			f[i][i] = w[a[i]];

		}

		for (int len = 2; len <= n; len++) {

			for (int i = 1; i <= n - len + 1; i++) {

				int l = i, r = i + len - 1;

				f[l][r] = min(f[l + 1][r], f[l][r - 1]) + pre[r] - pre[l - 1];

				for (int k = l + 1; k <= r - 1; k++) {

					f[l][r] = min(f[l][k - 1] + f[k + 1][r] + pre[r] - pre[l - 1], f[l][r]);

				}

			}

		}

		cout << f[1][n] << endl;

	}

}

/**********************************************************************

	Problem: 1980

	User: Artoriax

	Language: C++

	Result: AC

	Time:152 ms

	Memory:2516 kb

**********************************************************************/

巴特西

CSU-1980 不堪重负的树

CSU-1980 不堪重负的树

Description

Input

Output

Sample Input

Sample Output

Hint

题解

最新文章

热门文章