樹形DP的關鍵在於如何處理遞歸返回的信息。這題dp[i][0]表示不選i點時當前最高權值。dp[i][1]表示選i點時當前最高權值。狀態轉移方程：dp[u][[0]+=max(dp[v][0],dp[v][1]),dp[u][1]+=dp[v][0];
代碼如下：
#include #include #include #include #include #include #include #include #include using namespace std; #define LL __int64 #define pi acos(-1.0) const int mod=100000000; const int INF=0x3f3f3f3f; const double eqs=1e-8; int dp[7000][2], c[7000], vis[7000]; int head[7000], cnt, n; struct node { int u, v, next; }edge[100000]; void add(int u, int v) { edge[cnt].v=v; edge[cnt].next=head[u]; head[u]=cnt++; } void dfs(int u) { vis[u]=1; dp[u][1]=c[u]; for(int i=head[u];i+1;i=edge[i].next){ int v=edge[i].v; if(!vis[v]){ dfs(v); dp[u][0]+=max(dp[v][0],dp[v][1]); dp[u][1]+=dp[v][0]; } } } void init() { memset(vis,0,sizeof(vis)); memset(head,-1,sizeof(head)); cnt=0; memset(dp,0,sizeof(dp)); } int main() { int i, j, u, v; while(scanf("%d",&n)!=EOF){ for(i=1;i<=n;i++){ scanf("%d",&c[i]); } init(); while(scanf("%d%d",&u,&v)!=EOF&&u&&v){ add(u,v); add(v,u); } dfs(1); printf("%d\n",max(dp[1][0],dp[1][1])); } return 0; }
二叉樹的非遞歸遍歷--京東2015筆試回憶 題目回憶：
基於lucene的案例開發：ClassUtil &a
Problem Description Alice and
hdu1254 推箱子（bfs+bfs） 推箱子 Time
2016年藍橋杯C/C++B組 第一次參加藍橋杯，也是有很多
hdu4082 Hou Yi's secre
