洛谷 P1040加分二叉树

古城微笑少年丶 2023-05-21 08:41 7阅读 0赞

题目传送门：[https://www.luogu.com.cn/problem/P1040][https_www.luogu.com.cn_problem_P1040]

1. 这个题的求最大加分二叉树的过程，类似石子合并问题。

因为是1.2.3.4...n是中序遍历，所以当以k为某子树根时，1~k-1构成左子树，k+1~n构成右子树。很符合石子问题。

另dp\[ i \]\[ j \]表示由 i 节点到 j 节点所组成的子树的最大加分。

则dp\[ i \]\[ j \] = dp\[ i \]\[ k - 1 \] \* dp\[ k + 1 \]\[ j \] + score\[ k \];

其中k表示由 i 到 j 节点组成子树的根，i=<k<=j,我们要选择一个最好的K，使得二叉树的加分最大。score\[k\]表示K节点的分数。

则dp\[ i \]\[ j \] = max(dp\[ i \]\[ j \] , dp\[ i \]\[ k -1 \] \* dp\[ k + 1 \]\[ j \] + score\[ k \]); i<=K<=j

我们使用s\[ i \]\[ j \] = k 来记录K。

#include<iostream>
    #include<algorithm>
    #include<vector>
    #include<string>
    #include<sstream>
    #include<stack>
    #include<map>
    #include<set>
    using namespace std;
    const int MAXN = 35;
    const int INF = 0x7fffffff;
    
    struct Node{
    	int u;
    	int lc;
    	int rc;
    	Node(){
    		this->lc = -1;
    		this->rc = -1;
    	}
    	Node(int u,int lc,int rc){
    		this->u = u;
    		this->lc = lc;
    		this->rc = rc;
    	}
    };
    Node tree[MAXN];
    int a[MAXN];   //存储节点的分数 
    long long dp[MAXN][MAXN]; //dp[i][j] 表示：从i到j节点所组成子树的最大加分 
    int s[MAXN][MAXN];  //记录根节点，s[i][j]=u表示：从i到j节点所组成的最大加分子树的根节点为u 
    
    int dynamic(int n){
    	
    	//初始化 
    	dp[0][0] = 1;
    	for(int i=1;i<=n;i++){
    		dp[i][i] = a[i];
    		s[i][i] = i; 
    	}
    	
    	//状态转移方程 
    	for(int step=1;step<n;step++){
    		for(int i=1;i+step<=n;i++){
    			int j = i + step;
    			for(int k=i;k<=j;k++){
    				int ltree = k-1<i?1:dp[i][k-1];
    				int rtree = k+1>j?1:dp[k+1][j];
    				if(dp[i][j] < ltree*rtree+a[k]){
    					dp[i][j] = ltree*rtree+a[k];
    					s[i][j] = k;  //记录最优K 
    				}
    			}
    		}
    	}
    	
    	return dp[1][n];
    }
    
    //使用 s 数组建树 
    int createTree(int left,int right){
    	int root = s[left][right];
    	if(root-1 >= left){
    		tree[root].lc = createTree(left,root-1);
    	}else{
    		tree[root].lc = -1;
    	}
    	if(root+1 <= right){
    		tree[root].rc = createTree(root+1,right);	
    	}else{
    		tree[root].rc = -1;
    	}
    	return root;
    } 
    
    //前序遍历 
    vector<int> path;  //存储前序遍历的结果 
    void preOrder(int root){
    	if(root == -1){
    		return ;
    	}
    	path.push_back(tree[root].u);
    	preOrder(tree[root].lc);
    	preOrder(tree[root].rc);
    }
    
    int main(){
    	int n;
    	cin>>n;
    	for(int i=1;i<=n;i++){
    		cin>>a[i];
    		tree[i].u = i;
    	}
    	cout<<dynamic(n)<<endl;
    	int root = createTree(1,n);
    	preOrder(root);
    	
    	for(int i=0;i<path.size()-1;i++){
    		cout<<path[i]<<" ";
    	}
    	cout<<path[path.size()-1]<<endl;
        return 0;
    }

[https_www.luogu.com.cn_problem_P1040]: https://www.luogu.com.cn/problem/P1040