P1040 加分二叉树

最新推荐文章于 2025-04-26 17:47:42 发布

是三水不是泗水

最新推荐文章于 2025-04-26 17:47:42 发布

阅读量229

点赞数

分类专栏： C++/PAT/洛谷OJ

本文链接：https://blog.csdn.net/csg3140100993/article/details/82798756

版权

C++/PAT/洛谷OJ 专栏收录该内容

257 篇文章

订阅专栏

#include<bits/stdc++.h> 
using namespace std;
const int MAXN=33;
int root[MAXN][MAXN]={};
int dp[MAXN][MAXN]={};
vector<int> ppp;
void print(int l,int r){
    if(l>r) return;
    if(l==r){
    	cout<<l<<' ';return;
	}
    printf("%d ",root[l][r]);
    print(l,root[l][r]-1);
    print(root[l][r]+1,r);
}
int main()
{
	freopen("in.txt","r",stdin);
	int n;cin>>n;
	//fill(dp[0],dp[0]+MAXN*MAXN,1);
	for(int i=1;i<=n;i++){
		int w;cin>>w;
		dp[i][i]=w;
		dp[i][i-1]=1;//空树分值为1 
	}
	for(int i=n;i>=1;i--){//i是逆序枚举,用到dp[k+1][j]时已经提前计算出来了
		for(int j=i+1;j<=n;j++){
			for(int k=i;k<=j;k++){
				if(dp[i][j]<(dp[i][k-1]*dp[k+1][j]+dp[k][k])){
					dp[i][j]=dp[i][k-1]*dp[k+1][j]+dp[k][k];root[i][j]=k;
				}
			}
		}
	}
	cout<<dp[1][n]<<endl;
	print(1,n);
	return 0;
}

事实证明这道题逆序正序都可以做

#include<bits/stdc++.h> 
using namespace std;
const int MAXN=33;
int root[MAXN][MAXN]={};
int dp[MAXN][MAXN]={};
vector<int> ppp;
void print(int l,int r){
    if(l>r) return;
    if(l==r){
    	cout<<l<<' ';return;
	}
    printf("%d ",root[l][r]);
    print(l,root[l][r]-1);
    print(root[l][r]+1,r);
}
int main()
{
	freopen("in.txt","r",stdin);
	int n;cin>>n;
	//fill(dp[0],dp[0]+MAXN*MAXN,1);
	for(int i=1;i<=n;i++){
		int w;cin>>w;
		dp[i][i]=w;
		dp[i][i-1]=1;//空树分值为1 
	}
	for(int len=2;len<=n;len++){//以区间长度为元素进行正序dp
		for(int i=1;i<=n;i++){
			int j=i+len-1;
			for(int k=i;k<=j;k++){
				if(dp[i][j]<(dp[i][k-1]*dp[k+1][j]+dp[k][k])){
					dp[i][j]=dp[i][k-1]*dp[k+1][j]+dp[k][k];root[i][j]=k;
				}
			}
		}
	}
	cout<<dp[1][n]<<endl;
	print(1,n);
	return 0;
}