題幹:
小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。
其次就是考慮兩棵子樹如何合并的問題,其實也很簡單,無非就是讓這兩棵子樹的權值多加一遍,順便加一遍新的根節點的權值,換句話說,也就是對應中序周遊序列的區間和,這一點我們可以用字首和O1預處理出來,然後轉移就ok了。
#include<cstdio>
#include <assert.h>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define pm make_pair
using namespace std;
const int MAX = 2e2 + 6;
const ll INF = 0x3f3f;
ll w[MAX],p[MAX],val[MAX],sum[MAX];
ll dp[MAX][MAX];
int main()
{
int t,n;
cin>>t;
while(t--) {
scanf("%d",&n);
memset(sum,0,sizeof sum);
memset(dp,INF,sizeof dp);
for(int i = 1; i<=n; i++) scanf("%lld",w+i);
for(int i = 1; i<=n; i++) scanf("%lld",p+i);
for(int i = 1; i<=n; i++) val[i] = w[p[i]],sum[i] = sum[i-1] + val[i],dp[i][i]=val[i];
for(int len = 2; len <= n; len++) {
for(int l = 1; l+len-1 <= n; l++) {
int r = l + len - 1;
dp[l][r]=min(dp[l+1][r],dp[l][r-1])+sum[r]-sum[l-1];
for(int k = l+1; k<r; k++) {
dp[l][r] = min(dp[l][r],dp[l][k-1] + dp[k+1][r] + sum[r] - sum[l-1]);
}
}
}
printf("%lld\n",dp[1][n]);
}
return 0 ;
}