记录编号	419915	评测结果	AAAAAAA
题目名称	[NOIP 2003]加分二叉树	最终得分	100
用户昵称	玉带林中挂	是否通过	通过
代码语言	C++	运行时间	0.003 s
提交时间	2017-07-03 17:00:38	内存使用	0.34 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <stack>
#include <cstdlib>
#include <cmath>
#include <ctime>
using namespace std;
const int maxn=50;
long long dp[maxn][maxn];
long long data[maxn];
int p[maxn][maxn];
int n;
long long sdp(int l,int r)
{
    if(dp[l][r])return dp[l][r];
    if(l==r)
    {
        p[l][r]=l;
        return dp[l][r]=data[l];
    }
    if(r<l) return dp[l][r]=1;
    int ans=-1;
    int s;
    for(int k=l;k<=r;++k)
    {
        long long m=data[k]+sdp(l,k-1)*sdp(k+1,r);
        if(m>ans)
            ans=m,s=k;
    }
    p[l][r]=s;
    return dp[l][r]=ans;
}
void print(int l,int r)
{
    if(l>r)return;
    cout<<p[l][r]<<' ';
    print(l,p[l][r]-1);
    print(p[l][r]+1,r);
}
int main()
{
    freopen("jfecs.in","r",stdin);
	freopen("jfecs.out","w",stdout);
    cin>>n;
    for(int i=1;i<=n;++i)
        cin>>data[i];
    cout<<sdp(1,n)<<endl;
    print(1,n);
    return 0;
}