1238. 加分二叉树

Deuchie

一开始看成了状压 dp,给我写得怀疑人生了。其实这就是个普通的 dp。

顺便一提

前序遍历指的是先输出根结点,然后分别遍历左子树和右子树。中序遍历指的是先遍历左子树,再输出根结点,最后遍历右子树。后序遍历同理。

设 $dp(i, j)$ 包含中序遍历为 i..j(按惯例,左闭右开)的二叉树能组成的最大 point 和对应的前序遍历。那么有:

$$
dp(i, j) = \max_{k = i}^{j - 1}(dp(i, k) * dp(k + 1, j) + \text{node_points}(k))
$$

注意这里对边界情况有特别要求,上面的式子没有考虑。那就是如果有一个子树为空的话,上式中的子树分数为另一个子树的分数;如果两个都是空的(这是个叶子结点),那么这个树的分数就是这个结点的分数。

有了上面的式子,就可以写出代码了。下面的代码中使用的是闭区间,从 1 开始数数,所以和上面的式子有一点细节上的出入。

这个算法的复杂度是 $O(n^3)$,但是 $n$ 很小所以没有问题。

#include "bits/stdc++.h"
using u32 = uint32_t;
using u64 = uint64_t;

struct DpRecord {
    u64 point = 0;
    std::vector<u32> preorder_traversal;
};

int main() {
    u32 n;
    std::cin >> n;
    std::vector<u32> node_points(n + 1);
    for (u32 i = 1; i <= n; ++i) {
        std::cin >> node_points[i];
    }
    std::vector dp(n + 1, std::vector<DpRecord>(n + 1));
    for (u32 i = 1; i <= n; ++i) {
        // Special case for leaves.
        dp[i][i].point = node_points[i];
        dp[i][i].preorder_traversal.push_back(i);
    }
    for (u32 span_size = 2; span_size <= n; ++span_size) {
        for (u32 i = 1, j = i - 1 + span_size; j <= n; ++i, ++j) {
            u32 root;
            u64 potential_max;
            { // Special case for borders.
                auto const kIAsRoot = dp[i + 1][j].point + node_points[i];
                auto const kJAsRoot = dp[i][j - 1].point + node_points[j];
                if (kIAsRoot < kJAsRoot) {
                    root = j;
                    potential_max = kJAsRoot;
                } else {
                    root = i;
                    potential_max = kIAsRoot;
                }
            }
            for (u32 k = i + 1; k < j; ++k) {
                auto const kPoint = dp[i][k - 1].point * dp[k + 1][j].point + node_points[k];
                if (potential_max < kPoint) {
                    potential_max = kPoint;
                    root = k;
                }
            }
            dp[i][j].point = potential_max;
            auto& vec = dp[i][j].preorder_traversal;
            vec.push_back(root);
            for (auto const id : dp[i][root - 1].preorder_traversal) {
                vec.push_back(id);
            }
            for (auto const id : dp[root + 1][j].preorder_traversal) {
                vec.push_back(id);
            }
        }
    }
    std::cout << dp[1][n].point << '\n';
    for (auto const id : dp[1][n].preorder_traversal) {
        std::cout << id << ' ';
    }
    std::cout << '\n';
}
Andrew-Malcom

include

using namespace std;
const int maxn=35;
long long int score[maxn][maxn];
int vi[maxn];
int root[maxn][maxn];//用来存l-r之间的根节点
void printt(int l,int r)
{
        if(l>r) return;
        cout<<root[l][r]<<" ";
        printt(l,root[l][r]-1);
        printt(root[l][r]+1,r);
}
int main()
{
        ios::sync_with_stdio(false);
        cin.tie(0);
        int n;cin>>n;
        memset(score,0,sizeof(score));
        for(int i=1;i<=n;i++) cin>>vi[i];
        for(int i=1;i<=n;i++) root[i][i]=i;
        for(int i=1;i<=n;i++) score[i][i]=vi[i];
        for(int len=2;len<=n;len++){
                for(int i=1;i+len-1<=n;i++){
                        int j=i+len-1;
                        for(int k=i;k<=j;k++){
                                if(k==i){
                                        if(score[i][j]<score[k+1][j]+vi[k]){ 
                                                root[i][j]=k;
                                                score[i][j]=score[k+1][j]+vi[k];
                                        }
                                }
                                else if(k>i&&k<j){
                                        if(score[i][j]<score[i][k-1]*score[k+1][j]+vi[k]){ 
                                                root[i][j]=k;
                                                score[i][j]=score[i][k-1]*score[k+1][j]+vi[k];
                                        }
                                }
                                else if(k==j){
                                        if(score[i][j]<score[i][k-1]+vi[k]){
                                                root[i][j]=k;
                                                score[i][j]=score[i][k-1]+vi[k];
                                        }
                                }
                        }
                }
        }
        cout<<score[1][n]<<endl;
        printt(1,n);
}
Deuchie

兄弟,你这个格式出现了鬼畜。下次可以在代码前后加上这个:

\```cpp
\ code...
\```

(上面的没有反斜线)

你当前正在回复 博客/题目
存在问题!