企业官网建设流程全解析

wordpress如何建立网站,免费智能seo收录工具,网易企业邮箱的登录方法,网络架构师引子 树形DP是一种在树上的动态规划#xff0c;利用树的递归特性在树上进行状态转移。 树状DP主要分为两类#xff1a; 独立型#xff1a;兄弟节点间无相互约束依赖型#xff1a;兄弟节点间存在相互约束 独立型树状DP的特点是兄弟节点的状态互不影响#xff0c;各自独立计…引子树形DP是一种在树上的动态规划利用树的递归特性在树上进行状态转移。树状DP主要分为两类独立型兄弟节点间无相互约束依赖型兄弟节点间存在相互约束独立型树状DP的特点是兄弟节点的状态互不影响各自独立计算。就比如没有上司的舞会。依赖型树状DP则表现为兄弟节点状态之间存在制约关系状态分配需要权衡取舍如资源分配问题。就比如二叉苹果树。H P1352 没有上司的舞会简化题意有 n 个点他们的从属关系用一颗树来表示父结点是子结点的直接上司。每个点有一个点权求拿出若干个点且这若干个点的任意两点无从属关系的最大点权和。我们定义状态dp[i][0/1]表示以节点为根的子树的最大点权值。其中第二维取0表示节点 i 不参加舞会第二维取1表示节点 i 参加舞会状态转移方程如下设 v 为 x 的子节点当 x 不参加舞会时dp[x][0]max(dp[v][1],dp[v][0]);即子节点可以自由选择是否参加当 x 参加舞会时dp[x][1]dp[v][0];此时所有子节点都不能参加我们用DFS遍历这棵树在回溯时更新每个节点的DP。#includebits/stdc.husingnamespacestd;intr[6005],dp[6005][2];vectorintE[6005];voiddfs(intx,intfa){dp[x][1]r[x];for(inti0;iE[x].size();i){intvE[x][i];if(vfa)continue;dfs(v,x);dp[x][0]max(dp[v][1],dp[v][0]);dp[x][1]dp[v][0];}}intmain(){intn;cinn;for(inti1;in;i){cinr[i];}for(inti1;in;i){intu,v;cinuv;E[u].push_back(v);E[v].push_back(u);}dfs(1,0);coutmax(dp[1][0],dp[1][1]);return0;}J P2015 二叉苹果树题意给定一棵树n 个点有边权至少保留 q 条边求最大边权和。1.q 条边分到左子树多那么右子树就少兄弟节点间有数量约束考虑第二类树型DP。2.状态:dp[i][j]表示以 i 为根节点的子树保留至多 j 条边的最大边权和。3.答案:dp[1][q]4.状态转移intvE[x][i].v,wE[x][i].w;if(vfa)continue;dfs(v,x);sz[x]sz[v];for(intjmin(q,sz[x]);j0;j--){for(intk0;kmin(j-1,sz[v]);k){dp[x][j]max(dp[x][j],dp[v][k]dp[x][j-k-1]w);}}5.初始状态:dp[x][0]0#includebits/stdc.husingnamespacestd;structnode{intu,v,w;};vectornodeE[105];intn,q,sz[105],dp[105][105];voiddfs(intx,intfa){sz[x]1;for(inti0;iE[x].size();i){intvE[x][i].v,wE[x][i].w;if(vfa)continue;dfs(v,x);sz[x]sz[v];for(intjmin(q,sz[x]);j0;j--){for(intk0;kmin(j-1,sz[v]);k){dp[x][j]max(dp[x][j],dp[v][k]dp[x][j-k-1]w);}}}}intmain(){cinnq;for(inti1;in;i){intu,v,w;cinuvw;E[u].push_back({u,v,w});E[v].push_back({v,u,w});}dfs(1,0);coutdp[1][q];return0;}