贸易公司怎么做网站比较好,广东网站推广公司,网站变灰色,网站开发计划怎么写P2015 二叉苹果树
题意#xff1a;
一个完全二叉树#xff0c;n个点#xff0c;n-1个边#xff0c;每个边都有边权#xff0c;问保留q个边#xff0c;所能保留的最大边权是多少
题解#xff1a;
树形dp dp[u][i]表示u的子树上保留i条边#xff0c;至多保留的苹果数…P2015 二叉苹果树
题意
一个完全二叉树n个点n-1个边每个边都有边权问保留q个边所能保留的最大边权是多少
题解
树形dp dp[u][i]表示u的子树上保留i条边至多保留的苹果数目 如何建立状态转移方程呢 我们设v是u的一个子节点现在以u为根的子树要保留i个边那我们可以让v保留j个边u和v之间就有一个边u只需要保留i-j-1个边即可相当于u的儿子节点v分担了一部分任务另一部分其他负责 这样可得 dp[u][i] max(dp[u][i],dp[v][j]w[u][v]dp[u][i-j-1]) 循环i的时候为倒叙循环j的话无所谓 因为dp[u][i]还没更新时里面存的是除v之外的情况所以dp[u][i-j-1]表示的是除v节点的子树外其他保存i-j-1边的最大情况我们要用这个值去更新dp[u][i]更新后的dp[u][i]表示以u为根包含i个边(此时就包含v了)我们必须要逆序才能保证这一过程有01背包优化的那种感觉所以这个dp[u][i]相当于是优化的 for(int jmin(sz[u],q);j1;j--){for(int k0;kmin(sz[v],j-1);k){dp[u][j]max(dp[u][j],dp[u][j-k-1]dp[v][k]w);}}代码
#includebits/stdc.h
#define debug(a,b) printf(%s %d\n,a,b);
typedef long long ll;
using namespace std;inline int read(){int s0,w1;char chgetchar();while(ch0||ch9){if(ch-)w-1;chgetchar();}while(ch0ch9) ss*10ch-0,chgetchar();//s(s3)(s1)(ch^48);return s*w;
}
const int maxn220;
vectorpairint,int vec[maxn];
int dp[maxn][maxn];
int sz[maxn];
int n,q;
void dfs(int u,int fa){for(int i0;ivec[u].size();i){int vvec[u][i].first;int wvec[u][i].second;if(vfa)continue;dfs(v,u);sz[u]sz[v]1;for(int jmin(sz[u],q);j1;j--){for(int k0;kmin(sz[v],j-1);k){dp[u][j]max(dp[u][j],dp[u][j-k-1]dp[v][k]w);}}}
}
int main()
{cinnq;for(int i1;in;i){int u,v,w;cinuvw;vec[u].push_back(make_pair(v,w));vec[v].push_back(make_pair(u,w));}dfs(1,-1);coutdp[1][q];
}
