P1040 플러스 두 갈래 트리(트리 dp)
n개의 노드를 설정한 두 갈래 트리의 중서는 (1,2,3,..., n)이고 그 중에서 숫자는 1,2,3,..., n은 노드 번호이다.각 노드에는 하나의 점수(모두 정수)가 있고 i번째 노드의 점수는 di,tree와 그의 모든 나무는 하나의 가산점이 있으며 하나의 나무subtree(tree 자체도 포함)의 가산점 계산 방법은 다음과 같다.
subtree의 왼쪽 나무의 가산점× subtree의 오른쪽 나무의 가산점인 subtree의 뿌리의 분수.
만약 어떤 하위 나무가 비어 있다면 그 가산점을 1로 규정하고 잎의 가산점은 잎 노드 자체의 분수이다.그것의 빈 나무는 고려하지 않는다.
중서열(1,2,3,..., n)에 부합되고 가산점이 가장 높은 두 갈래 나무tree를 구해 보세요.출력 요구;
(1)tree의 최고 가산점
(2)tree의 앞 순서 반복
출력 형식 가져오기
입력 형식: 첫 번째 줄: 노드의 정수 n(n＜30)입니다.
두 번째 줄: n개의 공백으로 구분된 정수, 각 노드의 점수(분수＜100).
출력 형식: 첫 번째 줄: 최대 가산점을 주는 정수(결과는 400000000을 초과하지 않음).
두 번째 줄: n개의 공백으로 구분된 정수로 이 나무의 앞을 훑어봅니다.
내보내기 샘플 가져오기
샘플 입력 #1:5 5 7 1 2 10 샘플 출력 #1:145 3 1 2 4 5
#include" ";
dfs2(l,root[l][r]-1);
dfs2(root[l][r]+1,r);
}
long long dfs(int l,int r){
int now;//
if(l>r) return 1;
else{
if(best[l][r]==-1)//
{
for(int i=l;i<=r;i++)//
{
now=dfs(l,i-1)*dfs(i+1,r)+best[i][i];
if(now>best[l][r])
{
best[l][r]=now;
root[l][r]=i;
}
}
}
return best[l][r];
}
}
int main(){
int n;
memset(best,-1,sizeof(best));//
memset(root,-1,sizeof(root));
scanf("%d",&n);
for(int i=1;i<=n;i++){
cin>>best[i][i];
root[i][i]=i;
}
cout<1,n)<true;
dfs2(1,n);
} 트리 dp, 구간 dp와 유사
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
java 데이터 구조 2차원 트리의 실현 코드일.두 갈래 트리 인터페이스 2 노드 클래스 3. 두 갈래 나무 구현 이 글을 통해 여러분께 도움이 되었으면 좋겠습니다. 본 사이트에 대한 지지에 감사드립니다!...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
