每日一题 5月13日 加分二叉树 区间DP

题目链接：https://ac.nowcoder.com/acm/problem/16681
题目大意：

#include <bits/stdc++.h>
#define LL long long
using namespace std;

LL c[55], f[105][105], g[105][105];
LL DFS(int l, int r){
    if(l>r) return 1;
    if(l==r){
        g[l][r]=l;
        return c[l];
    }
    if(f[l][r]!=-1) return f[l][r];
    for(int k=l; k<=r; k++){
        LL ans=max(f[l][r], DFS(l, k-1)*DFS(k+1, r)+c[k]);
        if(ans>f[l][r]){
            f[l][r]=ans; g[l][r]=k;
        }
    }
    return f[l][r];
}

void put(int l, int r){

    if(l>r) return ;
    printf("%lld ", g[l][r]);
    put(l, g[l][r]-1);
    put(g[l][r]+1, r);
}

int main(){

    memset(f, -1, sizeof(f));
    int n; scanf("%d", &n);
    for(int i=1; i<=n; i++){
        scanf("%lld", &c[i]);
    }
    DFS(1, n);
    printf("%lld\n", f[1][n]);
    put(1, n);

    return 0;
}