코드 vs 1090 플러스 두 갈래 트리 (트리 DP)

2957 단어

1090 플러스 두 갈래 나무

 
2003년 NOIP 전국 리그 향상팀
시간 제한: 1s
공간 제한: 128000KB
제목 레벨: 다이아몬드 다이아몬드
풀다
실행 결과 보기
제목 설명 Description
n개의 노드를 설정한 두 갈래 트리의 중서는 (l, 2, 3,..., n)이고 그 중 숫자는 1,2,3,..., n은 노드 번호이다.각 노드에는 하나의 점수(모두 정정수)가 있고 j번째 노드의 점수는 di,tree와 그의 모든 나무는 하나의 가산점이 있다. 한 그루의 나무subtree(tree 자체도 포함)의 가산점 계산 방법은 다음과 같다.
subtree의 왼쪽 나무의 가산점× subtree의 오른쪽 나무의 가산점
만약에 어떤 자목을 위주로 한다면 그 가산점을 1로 규정하고 잎의 가산점은 잎 노드 자체의 분수이다.그것의 빈틈을 고려하지 않다
자목
중서열(1,2,3,..., n)에 부합되고 가산점이 가장 높은 두 갈래 나무tree를 구해 보세요.출력 요구;
(1)tree의 최고 가산점
(2)tree의 앞 순서 반복
 
 
이제 당신의 좋은 친구 XZ가 프로그램을 설계하여 정확한 답을 구하는 것을 도와주세요.
입력 설명 Input Description
첫 번째 줄: 하나의 정수 n(n<=30), 노드 개수입니다.
두 번째 줄: n개의 공백으로 구분된 정수, 각 노드의 점수(분수<=100)
출력 설명 Output Description
첫 번째 줄: 최대 가산점을 주는 정수 (결과는 400000000을 넘지 않음).
두 번째 줄: n개의 공백으로 구분된 정수로 이 나무의 앞을 훑어봅니다.
샘플 입력 샘플 입력
오
5 7 1 2 10
샘플 출력 샘플 출력
145
3 1 2 4 5
데이터 범위 및 힌트 Data Size & Hint
n(n<=30)
분수<=100

분류 태그


문제: f[root][l][r]는 구간 l에서 r를 나타내고 루트를 서브트리로 하는 뿌리의 최대치를 나타낸다.
모든 상황은 한 번만 계산한다.
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int n,m;
long long c[100],f[100][100][100];
int rt[100][100],a[100][100],root[100][100];
long long   dfs(int root,int l,int r)
{
	if (f[root][l][r]!=-1) 
	 return f[root][l][r];
	if (l==r)
	 {
	 	rt[l][r]=l;
	 	f[l][l][r]=c[l];
	 	return f[l][l][r];
	 }
	long  left=0; long long  right=0;
	for (int i=l;i<root;i++)
	{
	 long long t=dfs(i,l,root-1);
	 if (left<t)
	  left=t,rt[l][root-1]=i;
    }
    for (int i=root+1;i<=r;i++)
    {
     long long t=dfs(i,root+1,r);
     if (right<t)
      right=t,rt[root+1][r]=i;
    }
    if (!left) left=1;
    if (!right) right=1;
    f[root][l][r]=left*right+c[root];
    return f[root][l][r];
}
void outp(int l,int r)
{
	if (r<l) return ;
	printf("%d ",a[l][r]);
	int t=a[l][r];
	outp(l,a[l][r]-1);
	outp(a[l][r]+1,r);
}
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	 scanf("%lld",&c[i]);
	memset(f,-1,sizeof(f));
	long long ans=0;
    for (int i=1;i<=n;i++)
    {
    	long long t=dfs(i,1,n);
    	//cout<<t<<endl;
    	if (ans<t)
    	{
    		ans=t; rt[1][n]=i;
    		for (int j=1;j<=n;j++)
    		 for (int k=j;k<=n;k++)
    		  a[j][k]=rt[j][k];
    	}
    }
    printf("%lld
",ans);
    outp(1,n);
}
GitHub README 스타일 지정
플러스 트리

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage