poj 2342

题意 :每个员工参加晚会都有一个欢乐值，但是不能和自己直属上司同时去
以i号人为根，dp [i][1]表示 i 号人出席的总价值最大值，dp[i][0]表示 i 号人不出席的总价值最大值。

方程：dp[i][0] +=Σ max(dp[son][0],dp[son][1]);

dp[i][1] +=Σ dp[son][0];
个人习惯：一次dfs出来所有的解，without记忆化搜索

#include <iostream>
#include <cstdio>
const int maxn = 6050;
int n;
int happy[maxn],fa[maxn];
bool book[maxn];
int dp[maxn][3];
using namespace std;
int Rt;
void init()
{
    int L,K;
    cin >> n;
    for(int i = 1; i <= n ;i++)
        scanf("%d",&happy[i]);
    while(1){
        scanf("%d%d",&L,&K);
        if(L == 0 && K == 0)
            break;
        fa[L] = K;
        book[L] = true;
    }
    for(int i = 1 ; i <= n;i++)
        if(book[i] == false)
            Rt  = i;      //找根节点
}

void dfs(int root)    //第二维1是选择，0是不选
{
    if(dp[root][1] != 0||dp[root][0] != 0)
        return;
    for(int i = 1; i <= n ;i++)
        if(fa[i] == root)
            dfs(i);

    for(int i = 1; i <= n ;i++){
        if(fa[i] == root){
            dp[root][1] += dp[i][0];
            dp[root][0] += max(dp[i][1],dp[i][0]);
        }
    }
    dp[root][1] += happy[root];
}

int main()
{
    init();
    dfs(Rt);
    cout << max(dp[Rt][0],dp[Rt][1]);
    return 0;
}

poj2486

题意：给一个n个节点的树，节点编号为1~n, 根节点为1, 每个节点有一个权值。
从根节点出发，走不超过k步，问最多可以获取多少权值？

dp1[i][j][k] : 第i个节点的儿子一共j条边k个节点已经考虑，且回到这个节点
dp2[i][j] :第i个节点的儿子一共j条边，且不回到这个节点

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int N,K;
const int maxn = 210; // ????
vector<int> ve[maxn];
int apple[maxn];
int dp1[maxn][maxn][maxn];//dp1[i][j][k] : 第i个节点的儿子共一共j条边k个节点已经考虑，且回到这个节点
int dp2[maxn][maxn][maxn];//dp2[i][j] :第i个节点的儿子共一共j条边，且不回到这个节点
int Deg[maxn] ;

void init()
{
    for(int i =1; i <= N ;i++) {
        scanf("%d",&apple[i]);
        ve[i].clear();
    }
    for(int j = 1; j < N; j++){
        int u,v;
        scanf("%d%d",&u,&v);
        ve[u].push_back(v);
        ve[v].push_back(u);
    }
}

void dfs(int fa , int x)
{
    Deg[x] = 0;
    for(int i = 0 ; i < ve[x].size();i++){
        if(ve[x][i]!=fa) {
            dfs(x,ve[x][i]);
            Deg[x] ++;
        }
    }
    //返回来
    dp1[x][0][0] = apple[x] ;
    int i = 0 ;
    for (int e = 0 ; e < ve[x].size() ; e ++ ) if (ve[x][e] != fa) { // i表示前i个子节点
        int y = ve[x][e];
        i ++ ; //cerr << "i=" << i << "\n" ;
        for(int j = 0;j<=K;j++){//给所有儿子节点j条边
            dp1[x][j][i] = dp1[x][j][i-1] ;//不要i个节点时
            for(int k = 0 ; k <= j;k++){ //给当前儿子节点k条边
                if (j-k-2>=0 && dp1[y][k][Deg[y]] + dp1[x][j-k-2][i-1] > dp1[x][j][i] ) {//选择第i个点，前面所有点获得j-k-2条
                    dp1[x][j][i] = dp1[y][k][Deg[y]] + dp1[x][j-k-2][i-1];
                }
            }
        }
     }
     //dp2[x][0][0] = apple[x];
     // cout << "x = "<<dp2[x][0][0] <<endl;
     i = 0;
     for(int e = 0 ;e < ve[x].size();e++) if(ve[x][e] != fa){
        int y = ve[x][e];
        i++;
        for(int j = 0 ; j <= K ;j++){
            dp2[x][j][i] = dp2[x][j][i-1];
            for(int k = 0 ; k<= j ;k++){
                if(j-k-1>=0){
                    dp2[x][j][i] =max( dp2[y][k][Deg[y]]+dp1[x][j-k-1][i-1] , dp2[x][j][i]);
                    dp2[x][j][i] =max( dp1[y][k][Deg[y]]+dp1[x][j-k-1][i-1] , dp2[x][j][i]);
                 //   if(x == 2 && j == 3 && i ==3) cout << "dp1[" << y <<"][" <<k <<"][" << Deg[y] <<"] = " <<dp1[y][k][Deg[y]] <<"; dp1["<< x <<"][" <<j-k-1 <<"][" <<i-1 <<"] = " <<dp1[x][j-k-1][i-1] <<"\n";
                    if(j-k-2 >= 0)
                       dp2[x][j][i] = max(dp2[x][j][i], dp1[y][k][Deg[y]]+dp2[x][j-k-2][i-1]);
                }
            }
        }
     }
}


int main()
{
    while(cin >> N>>K){
        init();
        dfs(-1,1);
        int ans = 0;
        for(int i = 0 ; i <= K ;i++){
            ans = max(ans,dp1[1][i][Deg[1]]);
            ans = max(ans,dp2[1][i][Deg[1]]);
        }
       cout << ans<<endl;
    }
    return 0;
}