比赛 动规 评测结果 AAAAAAA
题目名称 加分二叉树 最终得分 100
用户昵称 kZime 运行时间 0.001 s
代码语言 C++ 内存使用 0.34 MiB
提交时间 2017-06-19 22:05:47
显示代码纯文本
# include <bits/stdc++.h>
# define ll long long
using namespace std;
inline int gn() { 
    int k = 0, f = 1;
    char c = getchar();
    for(; !isdigit(c); c = getchar()) if(c == '-') f = -1;
    for(; isdigit(c); c = getchar()) k = k * 10 + c - '0';
    return k * f;
}
ll q[40][40], f[40][40], val[40];
int n;
ll dp(int l, int r) { 
    if(r + 1 == l) return 1;
    if(f[l][r]) return f[l][r];
    ll tmp, ans = -1;//保证有一个tmp
    for(int t, k = l; k <= r; k++) { 
        if((t = dp(l, k - 1) * dp(k + 1, r) + val[k]) > ans) { 
            ans = t;
            tmp = k;
        }
    }
    q[l][r] = tmp;
    return f[l][r] = ans;
}
void print(int l, int r) { 
    if(l > r) return;
    printf("%lld ", q[l][r]);
    print(l, q[l][r] - 1);
    print(q[l][r] + 1, r);
}
int main() { 
# ifndef LOCAL
    freopen("jfecs.in", "r", stdin);
    freopen("jfecs.out", "w", stdout);
# else 
    freopen("in", "r", stdin);
# endif
    n = gn();
    for(int i = 1; i <= n; i++) { 
        f[i][i] = val[i] = gn();
        q[i][i] = i;
    }
    printf("%lld\n", dp(1, n));
    print(1, n);
}