AcWing 479. 加分二叉树
原题链接
简单
作者:
lyc_6
,
2020-12-31 19:49:00
,
所有人可见
,
阅读 563
#include <bits/stdc++.h>
using namespace std;
int R[1001][1001], n, f[1005][1005], a[100005];
void travel(int l, int r)
{
if (l > r) return;
int k = R[l][r];
cout << k << ' ';
travel(l, k - 1);
travel(k + 1, r);
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= n + 1; i++)
f[i][i - 1] = 1, f[i][i] = a[i], R[i][i] = i;
for (int i = n - 1; i >= 1; i--)
for (int j = i + 1; j <= n; j++)
for (int k = i; k <= j; k++)
{
int t = f[i][k - 1] * f[k + 1][j] + a[k];
if (f[i][j] < t) f[i][j] = t, R[i][j] = k;
}
cout << f[1][n] << endl;
travel(1, n);
return 0;
}