luoguP1040 区间DP(记忆化加分二叉树

dp[l][r]记录中序序列为l, l+1..r的最大加分值

root[l][r]记录这个序列的根节点

转移

i 为根节点

dp[l][r] = max(dp[l][i-1]*dp[l+1][r]+a[i], dp[l][r])

顺势更新root[l][r]

 1 #include <bits/stdc++.h>
 2 #define pb push_back
 3 #define po pop_back
 4 #define fi first
 5 #define se second
 6 
 7 using namespace std;
 8 
 9 typedef long long ll;
10 typedef pair<int, int> P;
11 
12 const int MAXN = 37;
13 const int MAXE = 1e5+7;
14 const int MAXV = 1e5+7;
15 const int INF = 0x3f3f3f3f;
16 
17 int a[MAXN];
18 
19 int dp[MAXN][MAXN];
20 int root[MAXN][MAXN];
21 int n;
22 
23 int dfs(int l, int r)
24 {
25     if (l > r) return 1; //leave
26     if (dp[l][r] > 0) return dp[l][r];
27     if (l == r)
28     {
29         root[l][r] = l;
30         dp[l][r] = a[l];
31         return dp[l][r];
32     }
33     for (int i = l; i <= r; i++)
34     {
35         int res = dfs(l, i-1)*dfs(i+1, r)+a[i];
36         if (res > dp[l][r])
37         {
38             dp[l][r] = res;
39             root[l][r] = i;
40         }
41     }
42     return dp[l][r];
43 }
44 void print(int l, int r)
45 {
46     if (l > r) return ;
47     if (l == r) 
48     {
49         printf("%d ", root[l][l]);
50         return ;
51     }
52     printf("%d ", root[l][r]);
53     print(l, root[l][r]-1);
54     print(root[l][r]+1, r);
55 }
56 int main()
57 {
58     //freopen("in.txt", "r", stdin);
59     while (cin >> n)
60     {
61         for (int i = 1; i <= n; i++) cin >> a[i];
62         memset(dp, 0, sizeof(dp));
63         cout << dfs(1, n) << endl;
64         print(1, n);
65         cout << endl;
66     }
67     return 0;
68 
69 }

View Code

luoguP1040 区间DP(记忆化 加分二叉树

luoguP1040 区间DP(记忆化加分二叉树