POJ 2486 애플 트 리 트 리 DP+패 킷 백 팩

링크:http://poj.org/problem?id=2486
제목:(사과)나무 한 그루,나무 에 N 개의 결점(N<=100)이 있 고 출발점 은 결점 1 이다.각 결점 에 몇 개의 사과 가 있 는데 저 는 K 걸음 조작(K<=200)을 할 수 있 습 니 다.매번 조작 은 현재 의 결점 에서 인접 한 결점 으로 이동 하고 인접 한 결점 에 도착 한 후에 위의 모든 사 과 를 먹 으 며 사과 가 더 이상 자라 지 않 습 니 다.인접 한 것 은 두 결점 사이 에 가장자리 가 연결 되 어 있다 는 것 을 말 합 니 다.K 스텝 조작 후 최대 몇 개의 사 과 를 먹 을 수 있 는 지 물 었 다.
사고방식:처음에 시 작 했 을 때 일반적인 나무 가방 문제 라 고 생각 했 습 니 다.dp[i][j]는 i 를 뿌리 로 하 는 나무 에서 j 개의 결점 에서 먹 을 수 있 는 사과 수 를 걸 어서 상 태 를 옮 기 는 것 을 대표 합 니 다.그러나 이렇게 옮 기 면 매번 의 이동 소 모 는 2(한 번)입 니 다.그러나 나타 날 수 있 는 상황 은 출발점 으로 돌아 가지 않 고 특정한 점 에 가서 멈 추고 앞으로 가지 않 는 것 입 니 다.
이렇게 위의 상태 이동 은 요 구 를 만족 시 킬 수 없다.그래서 dp[i][j][k]로 확장 해 야 합 니 다.
k=0,마지막 에 i 의 서브 트 리 에 멈 춰 서 결점 i 로 돌아 가지 않 는 것 을 대표 합 니 다.k=1 은 i 의 서브 트 리 에서 j 의 결점 을 걷 고 마지막 에 결점 j 로 돌 아 왔 다 는 것 을 의미한다.
상태 이동 방정식:
dp[u][i+2][1]=max(dp[u][i+2][1],dp[u][i-j][1]+dp[v][j][1]);뿌리 결점 으로 돌아 가 는 상황 은 자 결점 으로 돌아 가 는 상황 을 통 해 미 룰 수 있다 는 뜻 이다.dp[u][i+1][0]=max(dp[u][i+1][0],dp[u][i-j][1]+dp[v][j][0]);뿌리 결점 으로 돌아 가지 않 는 상황 은 원래 뿌리 결점 으로 돌아 가 는 상황 을 하위 결점 으로 돌아 가지 않 는 상황 에서 업데이트 할 수 있 음 을 나타 낸다.dp[u][i+2][0]=max(dp[u][i+2][0],dp[u][i-j][0]+dp[v][j][1]);뿌리 결점 으로 돌아 가지 않 는 상황 은 원래 뿌리 결점 으로 돌아 가지 않 는 상황 을 하위 결점 으로 돌아 가 는 상황 에서 업데이트 할 수 있 음 을 나타 낸다.
이 패 킷 은 일종 의 사상 적 인 패 킷 을 나타 낸다.왜냐하면 dp[i][j][0]과 dp[i][j][1]가 대표 하 는 두 가지 상황 은 모순 되 기 때문에 동시에 나타 날 수 없 을 것 이다.마지막 으로 루트 노드 로 업데이트 할 때 모든 상태 에서 가장 큰 값 이 답 입 니 다.
코드:

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include