比赛 |
动规 |
评测结果 |
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);
}