poj1741，|POJ 2342|動態規劃|Anniversary party

http://poj.org/problem?id=2342

樹形DP基礎題，具體看注釋。

設狀態f[i][0]為i不來，f[i][1]為i要來

f[r][1] += ?f[i][0]; ? //r要來，i為r的下屬
f[r][0] += ?max(f[i][0], f[i][1]);?//r不來，i為r的下屬

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#define ms(i,j) memset(i, j, sizeof(i));
using namespace std;
const int maxn = 6005;
int f[maxn][2];
bool visit[maxn];
int father[maxn];
int n;
void dfs(int r)
{visit[r] = true;for (int i=1;i<=n;i++){if (!visit[i]&&father[i]==r)//沒有訪問過的點并且i是r的下屬{dfs(i);//向葉子結點DFS，在葉子節點DPf[r][1] +=  f[i][0];f[r][0] +=  max(f[i][0], f[i][1]);} }
}
int main()
{while (scanf("%d", &n)==1){ms(f,0);ms(visit, false);ms(father, 0);for (int i=1;i<=n;i++) scanf("%d", &f[i][1]);int root = 0;//找最大權利的監督者(樹根) int l,k;while (scanf("%d%d", &l, &k)==2&&(l||k)){father[l] = k;//k監督l if (root==l){root = k;}}dfs(root);printf("%d\n", max(f[root][0], f[root][1]));}return 0;
}