POJ2486[트리 DP]

제목:

나무 한 그루를 주고 1부터 걷는다. k보를 걸으면 닿을 수 있는 최대 권한과.

아이디어:

우리는 1이라는 노드에서 K보를 걷는 데 얻는 최대치를 요구하기 때문에 dp는 >>>>>dp[node][k]: 이 노드에서 k보를 걷는 최대치를 쉽게 생각할 수 있다.그러나 상태가 이동할 때 하위 노드에서 모 노드와 어떤 관계를 맺는지 잘 알 수 없을 것 같다.그래서 틀에 박힌 말: 어떤 노드에서 그는 결국 자신으로 돌아갈 수 없을까 고민한다.그럼 옮기기 쉬워요.[i] [j] [j][0] 대표는 노드 i에서 j걸음으로 i로 돌아가는 최대치/dp[i] [j][j][j][j][j][0]는 노드 i에서 j걸음으로 i걸음으로 돌아가지 않는 최대치[son][son] [j][j][i][j][j][j][j][i][j][j][i][j][[j][[j][j][j][j][[j][j][j][[j][j][[j][[j][[j][j]] [father] [1] [1][1] [1] [1] [1] [1] [1] [j]]]][pj]][j]][자, 초기화는요?각 노드는 0걸음으로 자체로 돌아갑니다:val[node];모든 노드가 아무리 걸어도 최소한은 그 자체의 가치라는 뜻이다.PS: 이동 중 한 군데, 처음에는 의심스러웠지만

  for(int j=k;j>=1;j--){
      for(p=1;p<=j;p++){

       }
  }

왜 내 안에서 걸음걸이가 적은 노드를 호출하려고 하는데, 걸음걸이가 작은 노드를 먼저 갱신하지 않고 큰 노드를 먼저 갱신합니까?0/1배낭과 유사합니다. 왜냐하면 저는 매번 이 노드를 한 번만 사용할 수 있기 때문입니다. 만약에 작은 것을 먼저 열거하고 작은 것을 찾으면 이 노드는 한 번만 찾은 것이 아닙니다.그렇다면 나는 걸음 수가 작은 dp값에 대해 초기값인가?틀림없이 아니야, 그 걸음 수가 작은 dp값이 다른 son 노드에서 업데이트되었잖아.

Code:

const int N=1e2+10;
struct Edge{
    int v;
    int Next;
}edge[N<<1];
int head[N],tol;
int n,k,val[N];
int dp[N][N<<1][2];
void init(){
    tol=0;
    memset(head,-1,sizeof(head));
    memset(dp,0,sizeof(dp));
}
void add(int u,int v){
    edge[tol].v=v;
    edge[tol].Next=head[u];
    head[u]=tol++;
}
bool vis[N];
void DFS(int u){
    int j,p;
    for(int i=head[u];~i;i=edge[i].Next){
        int v=edge[i].v;
        if(vis[v]) continue;
        vis[v]=true;
        DFS(v);
        for(int j=k;j>=1;j--){
                for(p=1;p<=j;p++){
                    if(p>=2){
                        dp[u][j][0]=max(dp[u][j][0],dp[v][p-2][0]+dp[u][j-p][0]);
                        dp[u][j][1]=max(dp[u][j][1],dp[v][p-2][0]+dp[u][j-p][1]);
                    }
                    dp[u][j][1]=max(dp[u][j][1],dp[v][p-1][1]+dp[u][j-p][0]);
                }
        }
    }
}

int main(){
    int u,v;
    while(~scanf("%d%d",&n,&k)){
        init();
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&val[i]);
            for(int j=0;j<=k;j++)
                dp[i][j][0]=dp[i][j][1]=val[i];
        }
        for(int i=1;iscanf("%d%d",&u,&v);
            add(u,v);
            add(v,u);
        }
        memset(vis,false,sizeof(vis));
        vis[1]=true;
        DFS(1);
        printf("%d
",max(dp[1][k][0],dp[1][k][1]));
    }
    return 0;
}