낙곡 P1040 플러스 두 갈래 나무

https://www.luogu.org/problemnew/show/P1040

제목:

n n n 개의 노드가 있는 두 갈래 나무는 노드마다 하나의 점수가 있고 모든 자나무에도 점수가 있다. 각 자나무의 점수 계산 방법은 다음과 같다.× 오른쪽에 있는 나무의 가산점인 ubtr의 뿌리 점수.subtree의 왼쪽 나무의 가산점× subtreesubtree의 오른쪽 나무의 가산점인 subtreesubtree의 뿌리의 분수.subtree의 왼쪽 나무의 가산점×subtreesubtree의 오른쪽 나무의 가산점인 subtreesubtree의 뿌리의 분수.만약 어떤 하위 나무가 비어 있다면 그 가산점을 1로 규정하고 잎의 가산점은 잎 노드 자체의 분수이다.그것의 빈자 나무를 고려하지 않고 중서에 부합되는 두 갈래 나무 tr e tree tree (1,2,3,..., n) (1,2,3,..., n) (1,2,3,..., n) 를 시험적으로 구하십시오.출력 요구;(1)t r e tree tree의 최고 가산점 (2)t r e tree tree의 앞 순서 반복

생각:

우리는 dp[m][i][j]dp[m][i][j]dp[m][i][j]로 mm를 뿌리로 하고 자수는 i−ji-j의 나무의 최대 득점, sum[l]sum[l][r][r][r]로 자수 노드를 대표하는 i−ji-j의 자수의 최대 득점을 나타낸다. 그러면 dp[m][i]= max(dp[m]][i], (s u m [i][m−1]∗s u m [m + 1][j])∗a [m],su m [i] [j] = m a x (dp [m] [i] [j], su m [i] [j]) dp [m] [i] [j], (sum [i] [m-1] *sum [m+1] [j])* a[m],sum [i]=max (dp [m] [j],sum [i]) dp [m] [j], [i][m−1]∗sum[m+1][j]∗a[m]),sum[i][j]=max(dp[m][i][j],sum[i][j]),이렇게 상태 이동을 다 썼습니다. 뒤에 이 나무를 출력합니다. 구간의 최대치를 루트로 찾을 때마다그리고 왼쪽으로 오른쪽으로 돌아갑니다.

void First(int l, int r) {
    int Max = 0, u = -1;
    for (int i = l; i <= r; i ++) {
        if(Max < dp[i][l][r]) {
            Max = dp[i][l][r];
            u = i;
        }
    }
    if(l == 1 && r == n) printf("%lld
", Max);
    printf("%d ", u);
    if(u - 1 >= l) First(l, u-1);
    if(u + 1 <= r) First(u+1, r);
}

AC 코드:

#include

using namespace std;

#define LL long long
const int maxn = 1e5 + 5;
const int inf = 0x3f3f3f3f;
const int Mod = 1e9 + 7;
const double eps = 1e-8;
typedef pair<int, int> psi;

void fre() {
    if(freopen(" P1040.txt", "r", stdin) == NULL)
        system("touch  P1040.txt");
    freopen(" P1040.txt", "r", stdin);
}

LL dp[40][40][40], a[40], sum[40][40];
int n;

void First(int l, int r) {
    int Max = 0, u = -1;
    for (int i = l; i <= r; i ++) {
        if(Max < dp[i][l][r]) {
            Max = dp[i][l][r];
            u = i;
        }
    }
    if(l == 1 && r == n) printf("%lld
", Max);
    printf("%d ", u);
    if(u - 1 >= l) First(l, u-1);
    if(u + 1 <= r) First(u+1, r);
}

int main(int argc, char *args[]) {
    fre();
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++) scanf("%lld", &a[i]);
    memset(dp, 0, sizeof(dp));
    for (int i = 0; i <= n; i ++) 
        for (int j = 0; j <= n; j ++) 
            sum[i][j] = 1;
    for (int i = 1; i <= n; i ++) dp[i][i][i] = sum[i][i] = a[i];
    for (int k = 1; k <= n-1; k ++) {
        for (int l = 1; l + k <= n; l ++) {
            for (int m = l; m <= l + k; m ++) {
                dp[m][l][l+k] = max(dp[m][l][l+k], (sum[l][m-1] * sum[m+1][l+k]) + a[m]);
                sum[l][l+k] = max(sum[l][l+k], dp[m][l][l+k]);
             }
        }
    }
    First(1, n);
    return 0;
}