题解 P1040 【加分二叉树】

xun薰 · 2017-08-14 14:43:21 · 题解

这个题可以用动态规划或者记忆化搜索来做。因为如果要求加分最大的话，必须要求它的儿子结点

加分最大，所以就有了最优子阶段。我们可以枚举根来更新最大值。中序遍历有个特点，在中序遍

历这个序列上，某个点左边的序列一定是这个点的左子树，右边的序列，一定在这个点的右子树。

root[i,j]表示[i,j]这段序列的根，递归输出先序遍历。注意初始化，f[i][i]=v[i]，当序列只有I一个元素时，f[i][i]等于这个点本身

的权值，当l==r-1时，此时是空树设为1。

啦啦啦啦代码来啦 两种方法

动态规划 区间dp

#include<iostream>
#include<cstdio>
using namespace std;
int n,v[39],f[47][47],i,j,k,root[49][49];
void print(int l,int r){
    if(l>r)return;
    if(l==r){printf("%d ",l);return;}
    printf("%d ",root[l][r]);
    print(l,root[l][r]-1);
    print(root[l][r]+1,r);
}
int main() {
    scanf("%d",&n);
    for( i=1; i<=n; i++) scanf("%d",&v[i]);
    for(i=1; i<=n; i++) {f[i][i]=v[i];f[i][i-1]=1;}
    for(i=n; i>=1; i--)
        for(j=i+1; j<=n; j++)
            for(k=i; k<=j; k++) {
                if(f[i][j]<(f[i][k-1]*f[k+1][j]+f[k][k])) {
                    f[i][j]=f[i][k-1]*f[k+1][j]+f[k][k];
                    root[i][j]=k;
                }
            }
    printf("%d\n",f[1][n]);
    print(1,n);
    return 0;
}

记忆化搜索

#include<iostream>
#include<cstdio>
using namespace std;
int n,v[49],dp[49][49],root[49][49];
int ser(int l,int r){
    if(dp[l][r]>0)return dp[l][r];
    if(l==r)return v[l];
    if(r<l)return 1;
    for(int i=l;i<=r;i++){
        int p=ser(l,i-1)*ser(i+1,r)+dp[i][i];
        if(p>dp[l][r]){
            dp[l][r]=p;root[l][r]=i;
        }
    }
    return dp[l][r];
}
void print(int l,int r){
    if(r<l)return;
    if(l==r){printf("%d ",l);return;}
    printf("%d ",root[l][r]);
    print(l,root[l][r]-1);
    print(root[l][r]+1,r);
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&v[i]),dp[i][i]=v[i];
    printf("%d\n",ser(1,n));
    print(1,n);
    return 0;
}