Never or now.
本文从WordPress迁移而来, 查看全部WordPress迁移文章
树dp
12345678910
dp[u][0] : 自己建站,那么选儿子的时候就可以考虑掉3种情况,然后选一个最小的dp[u][0] = sigma min(dp[v][0] , dp[v][1] , dp[v][2]) + 1dp[u][1] : 父亲建站,那么选儿子的时候不能包括dp[v][1],因为u这里是没有站的dp[u][1] = sigma min(dp[v][0] , dp[v][2]);dp[u][2] : 儿子建站,那么肯定选了一个dp[v][0],但是这里要讨论一个问题如果存在一个或多个v,满足dp[v][0] < dp[v][2],那么肯定选最小的那个dp[v][0],其余的可以统一选min(dp[v][0],dp[v][2]),那么总的来说还是 dp[u][2] = sigma min(dp[v][0],dp[v][2]);但如果不存在,那么只好这样选, delta = dp[v][0] - dp[v][2];选delta最小的,作为那个dp[v][0]其余的都选min(dp[v][0],dp[v][2]); 这里甚至都不需要比较,其实就是dp[v][2]因而写成代码就是 dp[u][2] = min(dp[v][0] - dp[v][2]) + sigma min(dp[v][0] , dp[v][2]);
12345678910111213141516171819202122232425262728293031323334353637383940414243444546
#include <iostream>#include <cstdio>#include <cstring>#include <vector>using namespace std;#define N 10010#define INF 0x3f3f3f3f#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))#define pb push_backint n,dp[N][3];vector<int>e[N];void dfs(int u,int fa){ dp[u][0] = 1; int delta = INF,sum = 0; for(int i = 0; i < e[u].size(); i++){ int v = e[u][i]; if(v == fa) continue; dfs(v,u); dp[u][0] += min(dp[v][0],min(dp[v][1],dp[v][2])); dp[u][1] += min(dp[v][0],dp[v][2]); if(dp[v][0] - dp[v][2] < delta){ delta = dp[v][0] - dp[v][2]; } sum += min(dp[v][0],dp[v][2]); } if(delta < 0) dp[u][2] = sum; else dp[u][2] = sum + delta;}int main(){ while(scanf("%d",&n)!=EOF){ for(int i = 1; i <= n; i++) e[i].clear(); for(int i = 1; i < n; i++){ int u,v; scanf("%d%d",&u,&v); e[u].pb(v); e[v].pb(u); } cl(dp,0); dfs(1,-1); printf("%d\n",min(dp[1][0],dp[1][2])); } return 0;}