蓝桥---蓝桥舞会---树状dp

本文主要是介绍蓝桥---蓝桥舞会---树状dp，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

思路

一直没想到树状dp的递推公式是什么！！也没有想到dp[i][0]表示以i为根的最大快乐指数（i不去舞会），dp[i][1]表示以i为根的最大快乐指数（i去舞会）。感觉这道题是dp+dfs的结合，而上一道题(病毒溯源）是dfs中就直接记录了dp，所以没有体现出dp。树状dp感觉都是后根遍历，就比如这道题，会凭借这几行代码找到叶节点。而病毒溯源（一维dp）是没有记录在dp中，直接用dfs()来代替dp[]的内容。

for(int k=h[i];k!=-1;k=nxt[k]){int p=e[k];dfs(p);
}

参考AcWing---病毒溯源---树状dp-CSDN博客思路及写法，我们来做一下这道题。

C++代码

#include <iostream>
using namespace std;int h[100010];
int e[100010];
int nxt[100010];
int idx;
int n;
int a[100010];
int root[100010];
int dp[100010][2];//tql，第二个维度是选择or不选择，从来没这么考虑过
int head;void add(int a,int b){e[idx]=b;nxt[idx]=h[a];h[a]=idx++;
}int dfs(int i){//以i为根节点的最大快乐指数for(int k=h[i];k!=-1;k=nxt[k]){int p=e[k];dfs(p);}if(h[i]==-1){dp[i][0]=0;dp[i][1]=a[i];return a[i];}//dp[i][0]for(int k=h[i];k!=-1;k=nxt[k]){int p=e[k];dp[i][0]+=max(dp[p][1],dp[p][0]);}//dp[i][1]dp[i][1]=a[i];for(int k=h[i];k!=-1;k=nxt[k]){int p=e[k];dp[i][1]+=dp[p][0];}return max(dp[i][0],dp[i][1]);
}int main()
{ cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}/*初始化h*/for(int i=1;i<=n;i++){h[i]=-1;}/*建树*/for(int i=1;i<=n-1;i++){int u,v;cin>>u>>v;root[u]=1;add(v,u);}/*找根*/for(int i=1;i<=n;i++){if(root[i]==0){head=i;break;}}/*dfs*/cout<<dfs(head);return 0;
}

这篇关于蓝桥---蓝桥舞会---树状dp的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---