合肥网站排名优化公司,做网站便宜还是app便宜,宝塔面板上传自己做的网站,移动互联网的概念P1040-加分二叉树 这道题放在深度优先搜索的训练题中#xff0c;可是我实在没有看出来应该怎么搜索。看了题解以后才看出来是一个很简单的dp(我果然还是太菜了) 看出dp并且算出来最大的分数不是很复杂#xff0c;关键是输出给定中序遍历序列的二叉树的先序遍历#xff0c;要…P1040-加分二叉树 这道题放在深度优先搜索的训练题中可是我实在没有看出来应该怎么搜索。看了题解以后才看出来是一个很简单的dp(我果然还是太菜了) 看出dp并且算出来最大的分数不是很复杂关键是输出给定中序遍历序列的二叉树的先序遍历要用一个数组保存在dp的时候确定的根节点觉得不是很容易想到。 AC代码
#includecstdio
#includecstring
#includealgorithm
using namespace std;typedef long long ll;
const int MAXN35;
int n,first1;
int father[MAXN][MAXN];
ll score[MAXN][MAXN];ll search(int l,int r)
{ll tmp;if(lr) return 1; //如果lr说明没有子树应该为1乘起来以后就变成了只有左子树或者右子树//不用考虑叶子节点因为叶子节点的分数是它本身所以不会进行dpif(score[l][r]-1){for(int kl;kr;k){tmpsearch(l,k-1)*search(k1,r)score[k][k];if(tmpscore[l][r]){score[l][r]tmp;father[l][r]k; //保存这一段的根节点}}}return score[l][r];
}
void print(int l,int r)
{if(lr) return;if(first)first0;elseprintf( );printf(%d,father[l][r]);print(l,father[l][r]-1);print(father[l][r]1,r);
}
int main()
{scanf(%d,n);for(int i1;in;i){scanf(%lld,score[i][i]);father[i][i]i;for(int ji1;jn;j){score[i][j]-1;}}printf(%lld\n,search(1,n));print(1,n);return 0;
}
