POJ 1947 - Rebuilding Roads 트리 DP(일반 가방 이동)...

dp[x][y]는 x를 뿌리로 하는 자수가 y점으로 변해야 한다는 뜻인데...최소한 빼야 할 사이드 트리..최종 ans=max(dp[i][P]+t)
업데이트할 때는 두 가지 상황으로 나뉘는데...하나는 이 아이에게서 옮겨야 하는데..가방을 하나하나 만들어서...각 상태의 최소값을 업데이트합니다..아니면 이 아이를 잘라버리든지..그럼 모든 상태를 베기만 하면..
여기 매거진 01팩으로...잎사귀 노드를 얼마나 넣어야 될지 확실하지 않다는 뜻인데...잎 노드가 놓을 크기와 이 노드의 공간이 일일이 업데이트되고 있습니다.이런 콘셉트는 그냥 백팩...본질적으로 01배낭입니다.가방
매거 공간의 순서에 주의하세요.이렇게 하면 업데이트할 때 혼란이 없도록 보장할 수 있는데...
Program:

#include<iostream>

#include<stdio.h>

#include<string.h>

#include<set>

#include<ctime>

#include<algorithm>

#include<queue>

#include<cmath>

#include<map>

#define oo 100000007

#define ll long long

#define pi acos(-1.0)

#define MAXN 155

using namespace std;

vector<int> Tree[MAXN];

int dp[MAXN][MAXN],N,P,ans;

bool root[MAXN];

int dfs(int x)

{

      int i,j,y,m=Tree[x].size(),num=1,t,update;  

      for (i=0;i<=P;i++) dp[x][i]=oo;

      dp[x][1]=0;

      for (i=0;i<m;i++)

      {

             y=Tree[x][i];

             num+=dfs(y); 

             for (t=P;t>=1;t--)

             {

                    update=dp[x][t]+1;

                    for (j=1;j<=t;j++)

                       update=min(update,dp[x][t-j]+dp[y][j]);

                    dp[x][t]=update;

             }  //       

      }

      t=0;

      if (!root[x]) t++;

      if (dp[x][P]!=-1) ans=min(dp[x][P]+t,ans);

      return num;

}

int main()

{

      int i; 

      while (~scanf("%d%d",&N,&P))

      {

            for (i=1;i<=N;i++) Tree[i].clear();

            memset(root,true,sizeof(root));

            for (i=1;i<N;i++)

            {

                   int x,y;

                   scanf("%d%d",&x,&y);

                   Tree[x].push_back(y);

                   root[y]=false;

            }

            for (i=1;i<=N;i++)

               if (root[i]) break;

            ans=oo;

            dfs(i);

            printf("%d
",ans);

      }

      return 0;

}

POJ 1947 - Rebuilding Roads 트리 DP(일반 가방 이동)...

좋은 웹페이지 즐겨찾기