脚本宝典收集整理的这篇文章主要介绍了《P1040 [NOIP2003 提高组] 加分二叉树》,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
$一开始一直在想怎么构造出来的能更优,太傻了。$
$首先数据很小。然后就是有一个很显然的结论。$
$因为是中序遍历,如果以i为根,那么比i小的肯定被分割到它的左子树,比i大的肯定被分割到右子树$
$有了这点我们可以dp去找最优的根,因为这里显然让左右子树的分都尽量大是最优的,所以满足dp性,中间加个记忆化稍微优化一下就行。 $
// Author: levil #include<bits/stdc++.h> using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef long double ld; typedef pair<int,int> pii; const int N = 1e6 + 5; const int M = 1e4 + 5; const LL Mod = 998244353; #define rep(at,am,as) for(int at = am;at <= as;++at) #define ref(at,am,as) for(int at = am;at >= as;--at) #define INF 1e9 #define dbg(ax) cout << "now this num is " << ax << endl; inline long long ADD(long long x,long long y) { if(x + y < 0) return ((x + y) % Mod + Mod) % Mod; return (x + y) % Mod; } inline long long MUL(long long x,long long y) { if(x * y < 0) return ((x * y) % Mod + Mod) % Mod; return x * y % Mod; } inline long long DEC(long long x,long long y) { if(x - y < 0) return (x - y + Mod) % Mod; return (x - y) % Mod; } int n,rt[35][35]; LL dp[35][35],val[35]; LL dfs(int L,int r) { if(L > r) return 1; if(L == r) { rt[L][r] = L; return dp[L][r] = val[L]; } if(dp[L][r] != -1) return dp[L][r]; rep(i,L,r) { LL ltmp = dfs(L,i - 1); LL rtmp = dfs(i + 1,r); if(ltmp * rtmp + val[i] > dp[L][r]) { dp[L][r] = ltmp * rtmp + val[i]; rt[L][r] = i; } } return dp[L][r]; } void dfs1(int L,int r) { if(L > r) return ; printf("%d ",rt[L][r]); dfs1(L,rt[L][r] - 1); dfs1(rt[L][r] + 1,r); } void solve() { memset(dp,-1,sizeof(dp)); scanf("%d",&n); rep(i,1,n) scanf("%d",&val[i]); dfs(1,n); printf("%lldn",dp[1][n]); dfs1(1,n); } int main() { //int _; //for(scanf("%d",&_);_;_--) { solve(); //} system("pause"); return 0; }
以上是脚本宝典为你收集整理的《P1040 [NOIP2003 提高组] 加分二叉树》全部内容,希望文章能够帮你解决《P1040 [NOIP2003 提高组] 加分二叉树》所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。