POJ 1947 Rebuilding Roads(트리 DP)

제목:
n개의 점을 정한 나무, 최소한 몇 변을 삭제하면 p개의 노드가 있는 나무가 있습니다.
아이디어:
1. dp[u][p]는 u를 루트 노드로 하고 p개 노드가 가장 적게 삭제된 변수의 수를 나타낸다.초기화된 부분은 비교적 교묘하다. dp[u][1] = 0, 기타 할당 INFS
2. u의 아이 노드 v를 보존하면 dp[u][p]=min(dp[u][p-k]+dp[v][k])이 있고, 보존하지 않으면 dp[u][p]=dp[u][p]+1
3. 이 문제의 시간 복잡도는 O(p2*n)로 교차하는 범용 물품을 합친 O(p*n)의 해법을 채택할 수 없다. 왜냐하면 서브트리에 대해 상대적인 가방 용량이 고정되지 않기 때문이다.
 

#include <iostream>

#include <algorithm>

using namespace std;



const int MAXN = 160;

const int INFS = 0x3fffffff;

int dp[MAXN][MAXN], U[MAXN], V[MAXN];

bool vis[MAXN];



void treedp(int u, int vol, int n)

{

    for (int v = 0; v <= vol; ++v)

        dp[u][v] = INFS;

    dp[u][1] = 0;



    for (int i = 1; i < n; ++i)

    {

        if (u != U[i])

            continue ;



        treedp(V[i], vol, n);

        for (int v = vol; v >= 0; --v)

        {

            int ans = INFS;

            if (dp[u][v] != INFS)

                ans = dp[u][v] + 1;



            for (int p = 0; p <= v; ++p)

                if (dp[u][p] != INFS && dp[V[i]][v - p] != INFS)

                    ans = min(ans, dp[u][p] + dp[V[i]][v - p]);



            dp[u][v] = ans;

        }

    }

}



int main()

{

    int n, p;

    while (scanf("%d %d", &n, &p) != EOF)

    {

        memset(vis, false, sizeof(vis));

        for (int i = 1; i < n; ++i)

        {

            scanf("%d %d", &U[i], &V[i]);

            vis[V[i]] = true;

        }



        int rt;

        for (int i = 1; i <= n; ++i)

            if (!vis[i])

                rt = i;



        treedp(rt, p, n);



        int ans = dp[rt][p];

        for (int i = 1; i <= n; ++i)

            if (dp[i][p] < ans)

                ans = dp[i][p] + 1;



        printf("%d
", ans);

    }

    return 0;

}