나무 위의 dp 학습 노트

트리 DP:

선형 dp가 직면하는 문제는 일반적으로 선형 서열이나 그림이다.
나무의 dp는 나무 구조에서 dp를 진행하는 일종으로 각 단계에서 나무 관계를 나타낼 때도 나무 dp를 사용할 수 있다.
트리 dp 프로세스:
1. 문제가 숨은 나무(즉 나무를 직접적인 배경으로 하지 않음)라면 문제를 현성 나무로 전환하고 각 단계의 나무 형태의 관계를 저장해야 한다.
2. 트리의 데이터 구조에서 dp를 진행하지만 그 구해 방식은 선형 dp와 다르다.
계산 순서가 다르다.선형 dp는 두 가지 방향이 있는데 순추와 역추이다.나무형 dp도 두 방향이 있다.뿌리에서 잎까지의 선근을 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루
계산 방식이 다르다.선형은 전통적인 교체를 채택하고 나무형은 기억화, 귀환을 사용한다.
이전 예제:

P1352 상사 없는 무도회:

제목 설명

한 대학에는 1~N의 번호로 N명의 직원이 있다.그들 사이에는 종속관계가 있다. 즉, 그들의 관계는 교장을 뿌리로 하는 나무와 같고, 부결점은 자결점의 직접 상사이다.현재 주년 경축 연회가 있는데 연회에 한 명의 직원을 초대할 때마다 일정한 즐거움 지수가 증가한다. 그러나 만약에 어떤 직원의 상사가 무도회에 참가한다면 이 직원은 도저히 무도회에 참가하려고 하지 않을 것이다.그래서 어떤 직원을 초대하면 즐거움 지수가 가장 크고 가장 큰 즐거움 지수를 구할 수 있는지 프로그래밍을 해 보세요.

입력 출력 형식

입력 형식:
첫 번째 행에는 정수 N이 있습니다.(1<=N<=6000)
다음 N행, i+1행은 i번 직원의 쾌락지수 리를 나타낸다.(-128<=Ri<=127)
다음 N-1 행은 각 행에 정수 L, K 쌍을 입력합니다.K가 L의 직속 상관임을 나타낸다.
마지막 행에 0 0 을 입력합니다.
출력 형식:
가장 큰 즐거움 지수를 출력합니다.

출력 샘플 가져오기

샘플 입력 #1: 복사

7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5
0 0

출력 예제 #1: 복사

5

이 문제는 사실 최고의 상사를 뿌리로 한 숨은 나무다.나무의 어떤 지점 u에 대해서도 뿌리를 가진 자수의 최대 즐거움 지수는 두 가지 가능성치가 있을 수 있다.
만약에 자수의 최대 즐거움 지수와 u를 포함하지 않는 즐거움 지수, 즉 이 사람이 참가하지 않는다면 자수의 최대 즐거움 지수와 u를 위한 모든 자수(u의 아들을 뿌리로 하는 자수)의 최대 즐거움 지수의 누적.그러니까 나무 한 그루의 최대 즐거움 지수와 u를 포함하는 아들이나 u를 포함하지 않는 아들 중에서 가장 큰 것을 얻는다.
만약에 자수의 최대 즐거움 지수와 u를 포함하는 즐거움 지수, 즉 이 사람이 참가하면 그의 부하(자수)는 참가할 수 없다.
dp[u][0]는 u를 포함하지 않고 u를 뿌리로 하는 자수의 최대 즐거움 지수와.
dp[u][1]은 u를 포함하고 u를 뿌리로 하는 자수의 최대 즐거움 지수와.
뚜렷하다. dp[u][0]=0, dp[u][1]=u;
잎 노드에서 출발하여 아래에서 위로 순서대로 dp를 두루 훑어보다
방정식:
dp[u][0]=      Σ     max{dp[i][0],dp[i][1]}
아들집
dp[u][1]=dp[u][1](바로 u의 즐거움지수)+dp[u][0]
마지막 결과는 ans=max{dp[root][0],do[root][1]}
위 코드:

#include
#include
#include
#include
using namespace std;
int N,r[10001],a,b,root;
int dp[10001][2],son[10001],bro[10001];
bool is_son[10001];
void DP(int u){
	dp[u][0]=0;
	dp[u][1]=r[u];
	for(int i=son[u];i!=0;i=bro[i]){
		DP(i);//         
		dp[u][0]+=max(dp[i][0],dp[i][1]);
		dp[u][1]+=dp[i][0];
	}
}
int main(){
	cin>>N;
	memset(son,0,sizeof(son));
	memset(is_son,0,sizeof(is_son));
	for(int i=1;i<=N;i++){
		cin>>r[i];
	}
	for(int i=1;i>a>>b;
		bro[a]=son[b];//    
		son[b]=a;//a b    
		is_son[a]=true;//  a       
	}
	for(int i=1;i<=N;i++){
		if(!is_son[i]) root=i;//          
	}
	DP(root);
	cout<