POJ 2486(나무 가방 입문 문제)

제목:

하나의 나무, n개의 점(1-n), n-1개의 변, 각 점마다 하나의 권한이 있습니다. 1에서 출발하여 k보를 걸으면 가장 많이 범람할 수 있는 권한을 구합니다.

아이디어:

1. 우리는 뿌리 노드로 돌아가고 싶다.이 과정을 두 부분으로 나눈다. step1: 뿌리 노드 x에서 슨에 도착하고, 슨이 슨의 자수를 두루 훑어본 다음에 슨으로 돌아가고, 슨이 슨의 뿌리 노드 x로 돌아간다.step2: 남은 걸음수로 뿌리 노드 x의 나머지 자수를 두루 훑어보고 뿌리 노드 x로 돌아간다. 얻은 가치: dp[son][s-2][0]+dp[x][j-s][0]가 왜 s-2일까. 왜냐하면 son의 지점을 제외한 뿌리의 다른 지점은 j-s보를 사용했기 때문에 son까지는 s보만 남았고 뿌리에서 son까지는 두 걸음이 필요하기 때문이다.그래서 슨을 뿌리로 한 자수에서 걷는 것이 s-2걸음이다.우리는 dp[x][j][0]=max(dp[x][j][0], dp[son][s-2][0]+dp[x][j-s][0])를 얻었다.
2. 반드시 뿌리 노드로 돌아가는 것은 아니다.기왕 뿌리 노드 x로 돌아가는 것이 아니라면 마지막 위치는 어디일까요?우선 현재 결정된 하위 노드son을 뿌리 노드로 하는 하위 나무와 뿌리 노드 x의 나머지 하위 나무를 분리해서 고려해야 한다.case1: 마지막 위치는 하위 노드son을 뿌리 노드로 하는 나무에 있습니다.그러면 step1: 뿌리 노드에서 나머지 하위 나무를 옮겨다니며 최종적으로 뿌리 노드로 돌아간다.step2: 뿌리 노드에서son을 뿌리 노드로 하는 나무를 옮겨다니며 결국son으로 돌아가는 것은 아니다.우리는 dp[x][j][1]=max(dp[x][j][1], dp[son][s-1][1]+dp[x][j-s][0]])에서 많이 나온 그'1'은 위와 유사하고 뿌리 노드 x에서 하위 노드son까지의 한 걸음이다.case2: 마지막 위치는 나머지 하위 나무에 있습니다.step1: 뿌리 노드에서son을 뿌리 노드로 하는 자수를 두루 돌아다니다가 결국son으로 돌아가고 뿌리 노드 x.strep2로 돌아간다. 뿌리 노드에서 출발하여 나머지 자수를 두루 돌아다니면 결국son으로 돌아가는 것은 아니다. 행방을 알 수 없다.우리는 dp[x][j][1]=max(dp[x][j][1], dp[son][s-2][0]+dp[x][j-s][1])의 상태 전이 방정식을 얻었다.
그리고 제목이 반드시 k보를 가야 한다고 말하지 않았기 때문에 각 노드는 a[x]로 초기화됩니다.
ac 코드:

#include
#include
#include

using namespace std;

const int maxn=100+10;

int dp[maxn][maxn*2][2];

int head[maxn*2];
int cnt;
int a[maxn];
int n,k;

struct node{
    int v;
    int next;
    int w;
}p[maxn*2];

inline void addedge(int u,int v){
    p[++cnt].v=v;
    p[cnt].next=head[u];
    head[u]=cnt;
}

inline void init(){
    cnt=0;
    memset(head,-1,sizeof(head));
    memset(dp,0,sizeof(dp));
}

void dfs(int x,int fa){
    for(int i=0;i<=k;i++){
        dp[x][i][0]=dp[x][i][1]=a[x];
    }
    for(int e=head[x];e!=-1;e=p[e].next){
        int son=p[e].v;
        if(son==fa) continue;
        dfs(son,x);
        for(int j=k;j>=0;j--){
            for(int s=1;s<=j;s++){
                if(s>=2){
                    dp[x][j][0]=max(dp[x][j][0],dp[x][j-s][0]+dp[son][s-2][0]);
                }
                dp[x][j][1]=max(dp[x][j][1],dp[x][j-s][0]+dp[son][s-1][1]);
                if(s>=2){
                    dp[x][j][1]=max(dp[x][j][1],dp[x][j-s][1]+dp[son][s-2][0]);
                }
            }
        }
    }
}

int main(){
    while(scanf("%d%d",&n,&k)!=EOF){
        init();
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
        }
        int u,v;
        for(int i=1;i