题目链接: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; }