今天排位赛，以下的这道树DP想了我好囧！

一开始乱搞高斯消元。我第二次写高斯消元，还是自己默的。醉~~

然后发现，会出现自由元，为了求得最小值，不得二进制枚举了？但n<=100，我乱搞了一下，给我WA,不给我TLE

错了8、9次吧？心碎，只好用树dp做。（膜拜下林mm秒杀它。...Orz）
(后来看了下提交记录，16:41还是提交高斯消元，原来我交了10次高斯。。ft)

 

每个点记录三个状态：

A[u]  选u     u及其后代都亮

B[u]  不选u   u及其后代都亮

C[u]  不选u  u不亮，但是其后代都亮

显然有A[u]=∑C[v]   v是u的儿子

B[u],C[u]比较难求一点，需要多一次dp

假设u有n个儿子

dp[i,j]表示u的前i个儿子中有j个儿子是按了开关的（即A[v]）的最小值

dp[i,j] = min(dp[i-1,j]+B[v],dp[i-j,j-1]+A[v])

那么

B[u]=min(dp[n,k]); k为奇数

C[u]=min(dp[n,k]); k为偶数

 

  一个数据：
6
1 2
2 3
2 4
2 5
5 6
ans : 4


#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;

const int MAXN = 100;

vector<int>G[MAXN+10];

int A[MAXN+10],B[MAXN+10],C[MAXN+10];
int dp[MAXN+10][MAXN+10];

void treeDp(int u,int p)
{
    A[u]=1;
    vector<int>son;
    for(int i=0,size=G[u].size();i<size;i++)
    {
        int v=G[u][i];
        if(v==p)continue;
        treeDp(v,u);
        A[u]+=C[v];
        son.push_back(v);
    }
    int n=son.size();
    //dp一下 A[v]  B[v]
    dp[0][0]=0;
    for(int i=1;i<=n;i++)
    {
        int v=son[i-1];
        dp[i][0]=dp[i-1][0]+B[v];
        for(int j=1;j<=i;j++)
        {
            dp[i][j]=MAXN;
            if(i-1>=j)dp[i][j]=min(dp[i][j],dp[i-1][j]+B[v]);
            dp[i][j]=min(dp[i][j],dp[i-1][j-1]+A[v]);
        }
    }
    B[u]=C[u]=MAXN;
    for(int k=0;k<=n;k++)
    {
        if(k&1)B[u]=min(B[u],dp[n][k]);
        else C[u]=min(C[u],dp[n][k]);
    }
}
int main()
{
    int n;
    while(scanf("%d",&n),n)
    {
        for(int i=1;i<=n;i++)G[i].clear();
        for(int i=1;i<n;i++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            G[a].push_back(b);
            G[b].push_back(a);
        }
        treeDp(1,0);
        printf("%d\n",min(A[1],B[1]));
    }
    return 0;
}




2011.3.13 今天还出这题
数组开小了，wa了
n<=100 我开101也不行？ T_T 

状态表示为
dp[u,0] u父亲未亮，u及子树都已经点亮
dp[u,1] u父亲、u未亮，子树都亮
dp[u,2] u父亲、u及子树都亮了
转移是：
dp[u,0] <- 奇数个dp[v,2] + 剩下的dp[v,0]    v是u的儿子
dp[u,1] <- 偶数个dp[v,2] + 剩下的dp[v,0]
dp[u,2] <- 自身点亮1次 + 所有都是dp[v,1]
注意的是有一种思想：
方正点灯的顺序是无关的，所以在考虑u时，其子树该点的都已经点亮，u是最后点的
这样会清晰很多，就不会再去考虑v是否还点
所以实际情况从底往上点灯。




附：
 

There is a tree

Time Limit:1000MS  Memory Limit:65535K

题型: 编程题   语言: 无限制

Description

Tree is a graphy without loop and direction when defined in the graphy theory realm. There is a tree with a light and a button at each node. If the button is presses, the state of light at this node will switch to the other state, meaning that it will trun from ON to OFF, or from OFF to ON. Besides, the state of light in the neighbour nodes will also switch from ON to OFF or OFF to ON.

 

At the beginning, all the lights are in the state OFF. It is your task to find out at least how many operations of switching should be performed in order to make all the light ON.

 

Input

There are mutiple of data sets in the file.

        At each case, the first line contains an integer n, indicating the number of Nodes in the tree. (n<=100)

        Then following n – 1 lines. Each line contains a pair number of x y, meaning that Node x and Node y is linked with an edge.

        The input file is terminated by a 0.

Output

For each case, output the minimal number of operations to light up all the lights.

Sample Input

3

1 2

1 3

0

Sample Output

1

 
数据： in.txt  out.txt