트리 dp 입문 템플릿 문제 - 상사 없는 무도회(동적 기획)
2239 단어 동적 기획
한 대학에는 1~N의 번호로 N명의 직원이 있다.그들 사이에는 종속관계가 있다. 즉, 그들의 관계는 교장을 뿌리로 하는 나무와 같고, 부결점은 자결점의 직접 상사이다.현재 주년 경축 연회가 있는데 연회에 한 명의 직원을 초대할 때마다 일정한 즐거움 지수가 증가한다. 그러나 만약에 어떤 직원의 상사가 무도회에 참가한다면 이 직원은 도저히 무도회에 참가하려고 하지 않을 것이다.그래서 어떤 직원을 초대하면 즐거움 지수가 가장 크고 가장 큰 즐거움 지수를 구할 수 있는지 프로그래밍을 해 보세요.
입력 형식
N。(1<=N<=6000)
N ， i+1 i Ri。(-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
제목 링크(로곡)
나무형 dp는 먼저 개인이 나무형 dp에 대한 이해를 말하자면 사유상 사실 이것은 우리가 흔히 볼 수 있는 선형 dp와 차이가 많지 않다. 단지 그것이 점차적으로 추론하는 표현 형식은 선형이 아니라 나무형의 추론이다.코드의 쓰기 방법에 있어 흔히 볼 수 있는 선형 dp는 기본적으로 교체된 형식, 즉 for순환을 사용하는데 트리 dp는 나무처럼 점차적으로 추정되는 것이다. 모든 것은 dfs와 귀속적인 쓰기를 더 많이 사용한다.우리는 직접 위의 이 템플릿 문제를 가지고 나무 모양 dp를 느낀다.
제목에는 직원마다 두 가지 상황이 있는데, 하나는 참가하는 것이고, 다른 하나는 참가하지 않는 것이다.우리는 2차원 그룹으로 dp[n+1][2], dp[i][0]는 이 직원이 참가하지 않을 때의 최대 쾌락치를 표시하고, dp[i][1]는 이 직원이 참가하는 최대 쾌락치를 나타낼 수 있다.이 직원이 참가할 때 그의 모든 부하들은 참가할 수 없다. 즉 dp[y][0]는 모든 부하들이 참가하지 않는 값을 합치면 된다.이 직원이 참가하지 않을 때 그의 모든 부하들이 참가할 수도 있고 참가하지 않을 수도 있다. 최대치를 더하면 된다. 즉, 맥스(dp[y][0], dp[y][1])이다.글만 보면 무미건조하니 종이에 펜을 그려 놓으면 금방 이해할 수 있을 것 같다.
참조 코드:
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main
{
public static void main(String args[])
{
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
//
int[] rs=new int[n+1];
for(int i=1;i<=n;i++)
rs[i]=sc.nextInt();
//
List> ps=new ArrayList>();
for(int i=0;i<=n;i++)
ps.add(new ArrayList());
int[] book=new int[n+1];
for(int i=1;i> ps,int[] rs, int[][] dp, int root)
{
dp[root][1]=rs[root];
for(int i=0;i
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
01 가방, 완전 가방, 다중 가방 dp(동적 기획 입문 dp)01 가방은 2진법으로 직접 표시할 수 있지만 데이터 양이 너무 많으면 시간을 초과하는 것이 폭력이다.01 가방의 사상은 바로 이 물품에 대해 내가 넣은 가치가 큰지 안 넣은 가치가 큰지 비교하여 방정식 f[i][v...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
