【6.10校内test】T3 加分二叉树

加分二叉树【题目链接】

感觉我超废

这道题当时压根就不会qwq（我倒是挺适合写rand的qwq）

对于暴力的做法：

输入数据，定义数组men[i][i]=v[i]（输入的第二行）；
dfs：
1. dfs 1—n，首先是几个临界状态：
  1. 当左或右子树为空，即L>R(use L and R replace l and r to be clear)时，返回1
  2. 当L==R时，显然它的分数为它本身，所以return d[L] or d[R]
  3. 还有一个小优化，就是当我们之前已经算过某一段[L，R]时，可以直接拿来取用，即if(mem[l][r]>0)return mem[l][r];

优化的效果：优化前：优化后：效果还是很明显的；

4.然后枚举每个点做这棵子树的根（for循环）这里为了一会输出前序遍历，所以要开数组root[i][j]记录每一段的根是什么；

先判断L==R？输出L or R：继续；因为在dfs时我们并没有记录L==R时的root值（直接return 了）
判断输出解的范围，如果L>R显然接下来的输出都是无效的，直接return；
可以开始输出根root了，输出root[L][R]之后，再递归的输出左子树和右子树（先左后右）

以上就是暴力DFS的思路，以下是代码：

#include<iostream>
#include<cstdio>
using namespace std;
int n,v[31],mem[31][31],root[31][31];
int dfs(int l,int r){
    if(mem[l][r]>0)return mem[l][r];//当这个点已经被计算过时，直接返回 
    if(l==r)return v[l];//当只有一个点时，它的值就为本身 
    if(r<l)return 1;//当出现左右颠倒的情况，也就是空子树，加分为1 
    for(int i=l;i<=r;i++){//分别枚举每个点做子树的根 
        int p=dfs(l,i-1)*dfs(i+1,r)/*左子树的值×右子树的值*/+mem[i][i]/*+根结点的值*/;
        if(p>mem[l][r]){
            mem[l][r]=p;/*求最大值*/root[l][r]=i/*记录路径用来前序遍历*/;
        }
    }
    return mem[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(){
    freopen("binary.in","r",stdin);
    freopen("binary.out","w",stdout); 
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&v[i]),mem[i][i]=v[i];
    printf("%d
",dfs(1,n));
    print(1,n);
    return 0;
}

对于被称之为正解的做法：

区间dp的做法：

数组dp[i][j]，表示区间[i,j)内的最高加分；
几种情况：
1. 对于以一个点建子树，dp[i][i+1]（因为是开区间，所以后面要+1）就是对应的输入的加分
2. 对于以2~n个点建子树，需要一套for循环进行区间dp，最后的答案是dp[1][n+1]；区间dp如下：

第一层for循环l：枚举以几个点建子树，可以是2~n；

第二层for循环i：枚举一个区间，需满足i+l<=n+1（举个例子：n=5，以两个点建子树时，i的取值分别为1,2,3,4，相应的区间为[1,2],[2,3],[3,4],[4,5]）

第三层for循环k：枚举楼上划分出的区间内以哪个点为根，计算加分，记录其中的最大值（小注意：还要开一个数组用来前序遍历，遍历和dfs的思想是一样的，记录的话也一样，这里用w数组）；

样例：

#include <iostream>
using namespace std;
int n;
int d[31];
long long dp[31][32]; //dp[i][j] -> answer in [i,j)
int w[31][32];
void dfs(int l, int r)
{
    cout << w[l][r] << ' ';
    if (w[l][r] > l)
        dfs(l, w[l][r]);
    if (w[l][r] + 1 < r)
        dfs(w[l][r] + 1, r);
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> dp[i][i + 1], dp[i][i] = 1, w[i][i + 1] = i;
    for (int l = 2; l <= n; l++)
    {
        for (int i = 1; i + l <= n + 1; i++)
        {
            int j = i + l;
            for (int k = i; k < j; k++)
            {
                if (dp[i][k] * dp[k + 1][j] + dp[k][k + 1] > dp[i][j])
                {
                    dp[i][j] = dp[i][k] * dp[k + 1][j] + dp[k][k + 1];
                    w[i][j] = k;
                }
            }
        }
    }
    cout << dp[1][n + 1] << endl;
    dfs(1, n + 1);
}

end-