플러스 트리
플러스 트리
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의 앞 순서 반복
Input
첫 번째 줄: 정수 n(n<30)은 노드 개수입니다.두 번째 줄: n개의 공백으로 구분된 정수, 각 노드의 점수(분수<100).
Output
첫 번째 줄: 최대 가산점을 주는 정수 (결과는 400000000을 넘지 않음).두 번째 줄: n개의 공백으로 구분된 정수로 이 나무의 앞을 훑어봅니다.
Sample Input
5
5 7 1 2 10
Sample Output
145
3 1 2 4 5
HINT
Source
#include
using namespace std;
int n, a[101];
int opt[101][101];
int f[101][101];
int solve (int p, int q) {
if (f[p][q] != -1) {
return f[p][q];
}
if (p > q) {
f[p][q] = 1;
return 1;
}
else if (p == q) {
opt[p][p] = p;
f[p][q] = a[p];
return f[p][q];
}
int ans = 0;
for (int r = p; r <= q; r ++) {
int res = solve(p, r - 1) * solve(r + 1, q) + a[r];
if (res > ans) {
ans = res;
opt[p][q] = r;
}
}
f[p][q] = ans;
return f[p][q];
}
void proot(int p, int q) {
if (p > q) {
return ;
}
printf("%d ", opt[p][q]);
proot(p, opt[p][q] - 1);
proot(opt[p][q] + 1, q);
}
int main() {
cin >> n;
memset(f, -1, sizeof(f));
for (int i = 1; i <= n; i ++) {
scanf("%d", &a[i]);
}
cout << solve(1, n) << endl;
proot(1, n);
return 0;
}
역귀작법
#include
using namespace std;
int n, a[101];
int opt[101][101];
int f[101][101];
void print(int p, int q) {
if (p > q) return ;
printf ("%d ", opt[p][q]);
print(p, opt[p][q] - 1);
print(opt[p][q] + 1, q);
}
int main() {
cin >> n;
memset(f, -1, sizeof(f));
for (int i = 1; i <= n; i ++) {
scanf("%d", &a[i]);
f[i][i] = a[i];
f[i][i - 1] = 1;
opt[i][i] = i;
}
for (int len = 2; len <= n; len ++) {
for (int i = 1; i <= n; i ++) {
int j = i + len - 1;
for (int k = i; k <= j; k ++) {
if (f[i][j] < f[i][k - 1] * f[k + 1][j] + a[k]) {
f[i][j] = f[i][k - 1] * f[k + 1][j] + a[k];
opt[i][j] = k;
}
}
}
}
cout << f[1][n] << endl;
print(1, n);
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.