时间复杂度$O(n^2)$
(在n次搜索中访问了全部$O(n^2)$的状态,并且剪掉了所有的多余状态)
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 32;
int w[N], n, root[N][N], ans;
long long f[N][N];
long long dfs(int u, int lf, int rt)
{
long long lmax = 0, rmax = 0, t;
int l_id = -1, r_id = -1;
if (u > lf && !root[lf][u - 1]){
for (int l = lf; l < u; ++l) {
t = dfs(l, lf, u - 1);
if (lmax < t) {
lmax = t;
l_id = l;
}
}
root[lf][u - 1] = l_id;
f[lf][u - 1] = lmax;
}
if (u < rt && !root[u + 1][rt]){
for (int r = u + 1; r <= rt; ++r) {
t = dfs(r, u + 1, rt);
if (rmax < t) {
rmax = t;
r_id = r;
}
}
root[u + 1][rt] = r_id;
f[u + 1][rt] = rmax;
}
if (u == rt && u == lf) return w[u];
else if(u == rt) return f[lf][u - 1] + w[u];
else if(u == lf) return f[u + 1][rt] + w[u];
else return f[lf][u - 1] * f[u + 1][rt] + w[u];
}
long long solve()
{
long long res = 0, t;
for (int i = 1; i <= n; ++i) {
t = dfs(i, 1, n);
if (res < t) {
res = t;
ans = i;
}
}
return res;
}
void dfs2(int u, int l, int r)
{
cout << u << " ";
int lf = root[l][u - 1], rt = root[u + 1][r];
if(lf) dfs2(lf, l, u - 1);
if(rt) dfs2(rt, u + 1, r);
}
int main()
{
cin >> n;
for (int i = 1; i <= n; ++i) scanf("%d", &w[i]);
cout << solve() << endl;
dfs2(ans, 1, n);
return 0;
}