今天排位賽，以下的這道樹(shù)DP想了我好囧！

一開(kāi)始亂搞高斯消元。我第二次寫(xiě)高斯消元，還是自己默的。醉~~

然后發(fā)現(xiàn)，會(huì)出現(xiàn)自由元，為了求得最小值，不得二進(jìn)制枚舉了？但n<=100，我亂搞了一下，給我WA,不給我TLE

錯(cuò)了8、9次吧？心碎，只好用樹(shù)dp做。（膜拜下林mm秒殺它。...Orz）
(后來(lái)看了下提交記錄，16:41還是提交高斯消元，原來(lái)我交了10次高斯。。ft)

 

每個(gè)點(diǎn)記錄三個(gè)狀態(tài)：

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

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

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

顯然有A[u]=∑C[v]   v是u的兒子

B[u],C[u]比較難求一點(diǎn)，需要多一次dp

假設(shè)u有n個(gè)兒子

dp[i,j]表示u的前i個(gè)兒子中有j個(gè)兒子是按了開(kāi)關(guān)的（即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為奇數(shù)

C[u]=min(dp[n,k]); k為偶數(shù)

 

  一個(gè)數(shù)據(jù)：
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 今天還出這題
數(shù)組開(kāi)小了，wa了
n<=100 我開(kāi)101也不行？ T_T 

狀態(tài)表示為
dp[u,0] u父親未亮，u及子樹(shù)都已經(jīng)點(diǎn)亮
dp[u,1] u父親、u未亮，子樹(shù)都亮
dp[u,2] u父親、u及子樹(shù)都亮了
轉(zhuǎn)移是：
dp[u,0] <- 奇數(shù)個(gè)dp[v,2] + 剩下的dp[v,0]    v是u的兒子
dp[u,1] <- 偶數(shù)個(gè)dp[v,2] + 剩下的dp[v,0]
dp[u,2] <- 自身點(diǎn)亮1次 + 所有都是dp[v,1]
注意的是有一種思想：
方正點(diǎn)燈的順序是無(wú)關(guān)的，所以在考慮u時(shí)，其子樹(shù)該點(diǎn)的都已經(jīng)點(diǎn)亮，u是最后點(diǎn)的
這樣會(huì)清晰很多，就不會(huì)再去考慮v是否還點(diǎn)
所以實(shí)際情況從底往上點(diǎn)燈。




附：
 

There is a tree

Time Limit:1000MS  Memory Limit:65535K

題型: 編程題   語(yǔ)言: 無(wú)限制

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

 
數(shù)據(jù)： in.txt  out.txt