[bzoj1040]-[ZJOI2008]骑士

NOIP考完了,该来省选了……

先从简单的开始入手吧 : D

题目(bzoj)

这题一看就是个dp……O(n)的树形dp。

然后这就是个基环树dp,基环树dp的套路就是:断环成树,树形dp

所以就这么整吧!

dp[u][0]表示u这个点不选时的最大值,dp[u][1]表示选这个点时的最大值。

状态转移很好写,

dp[u][0]=∑max(dp[v][0],dp[v][1]),

dp[u][1]=∑dp[v][0],

初始值为dp[u][0]=0,dp[u][1]=a[u]。

设每次断的边的两个端点为x1,x2,并且强制这个点不能选,

那么ans就加上max(dp[x1][0],dp[x2][0]);

如果没有断环,就直接ans加上dp[i][0],

完毕。

另外注意一下重边的情况:也很简单,弄个时间戳标记一下即可。

 

发表评论