[NOIp2003]加分二叉树

一种树形dp的状态设计及树型结构表示法。

其中$dp[l][r]$表示编号$l\to r$节点的最大加分,$root[l][r]$表示编号$l\to r$节点的根。

自顶向下递归求解。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int MAXN = 31;

int n;
int credit[MAXN];
ll dp[MAXN][MAXN];
ll root[MAXN][MAXN];

ll search(int l, int r) {
    int now;
    if ( l > r )
        return 1;
    if ( dp[l][r] == -1 ) 
        for ( int i = l; i <= r; ++i ) {
            now = search(l, i - 1) * search(i + 1, r) + dp[i][i];

            if( now > dp[l][r] ) {
                  dp[l][r] = now; 
                root[l][r] = i;
              }
        }

    return dp[l][r];
}

void printtree(int l, int r) {
    if ( l > r )
        return;
    cout << root[l][r] << ' ';

    printtree(l, root[l][r] - 1);
    printtree(root[l][r] + 1, r);
}

int main() {
    ios::sync_with_stdio(false);

    cin >> n;

    for ( int i = 1; i <= n; ++i )
        for ( int j = i; j <= n; ++j )
            dp[i][j] = -1;
    

    for ( int i = 1; i <= n; ++i ) {
        cin >> dp[i][i];
        root[i][i] = i;
    }

    cout << search(1, n) << endl;
    printtree(1, n);

    return 0;
}
Last modification:October 4th, 2019 at 10:37 am
博客维护不易,如果你觉得我的文章有用,请随意赞赏

Leave a Comment