加分二叉树

题目：

思路

题意就是 建立一棵中序遍历为 （1，2，3，....,n）的树，求 的最大值

如果是叶子结点 值就是
如果只有左子树 值就是
如果只有右子树 值就是
如果左右子树都存在 值就是

ps：这里题意不明，题目说“若以某个子树为主，规定其加分为1”我实在是没看懂，还是问了队友才知道什么意思

有了上面那个递推式就知道这是区间dp了，dp[i][j]表示i到j是一棵树的最大值
所以转移方程就是 ： dp[ i ][ j ] = max(dp[ i ][ j ] , dp[ i ][ k - 1 ]*dp[ k + 1 ][ j ]+tree[ k ] ) 这里的k表示以k为根

这里有两种解法，可以枚举长度区间dp，也可以先建立底层，直接枚举i，j来dp

代码1

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
#pragma GCC optimize(3)
typedef long long ll;
#define INF 0x3f3f3f3f
const int mod = 1e9+7;
const int maxn = 200005;

inline ll read(){
    ll s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
ll tree[35];
ll dp[35][35],root[35][35];//root[ i ][ j ] 表示 i~j为树的值最大时根的位置
void dfs(int l,int r){
    if(l > r) return ;
    cout<<root[l][r]<<" ";
    dfs(l,root[l][r]-1);
    dfs(root[l][r]+1,r);
}
int main(){
    int n = read();
    for(int i = 1 ; i <= n ; ++i) tree[i] = read();
    ll tmp;
    for(int len = 1 ; len <= n ;++len){
        for(int i = 1 ; i <= n-len+1 ;++i){
            int j = i+len-1;
            for(int k = i ; k <= j ; ++k){
               if(k > i && k < j )  tmp = dp[i][k-1]*dp[k+1][j]+tree[k];
               else if(k == i && k == j)  tmp = tree[k];
                else if(k == i) tmp = dp[k+1][j]+tree[k];
                else tmp = dp[i][k-1] + tree[k];
                if(tmp>dp[i][j]){
                    dp[i][j] = tmp;
                    root[i][j] = k;
                }
            }
        }
    }
    cout<<dp[1][n]<<endl;
    dfs(1,n);
}

代码2

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
#pragma GCC optimize(3)
typedef long long ll;
#define INF 0x3f3f3f3f
const int mod = 1e9+7;
const int maxn = 1e5+5;

inline ll read(){
    ll s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
int a[35],dp[35][35];
void dfs(int l,int r){
    if(l>r)  return;
    if(l==r){
        printf("%d ",l);
        return;
    }
    for(int i=l;i<=r;++i){
        if(dp[l][r]==dp[l][i-1]*dp[i+1][r]+a[i]){
            printf("%d ",i);
            dfs(l,i-1),dfs(i+1,r);
            return;
        }
    }
}
int main(){
   int n = read();
    for(int i = 1;i <= n; ++i){
        a[i] = read();
        dp[i][i]=a[i];dp[i][i-1]=1;
    }
    dp[n+1][n]=1;
    for(int i=n;i;--i){
        for(int j=i+1;j<=n;++j){
            for(int k=i;k<=j;++k){
                dp[i][j]=max(dp[i][j],dp[i][k-1]*dp[k+1][j]+a[k]);
            }
        }
    }
    cout<<dp[1][n]<<endl;
    dfs(1,n);
    return 0;
}