今天排位賽，以下的這道樹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