玄关

#include<bits/stdc++.h>
using namespace std; 
#define int long long
const int N = 30 ;
int n ; 
int C[N];
int f[N][N][N];//f[x][l][r] x为根 区间[l,r]
int rt[N][N];//rt[l][r]为[l,r]最优解的根
vector<int> P;
int ans;
int dp(int x,int l,int r)
{
	if(f[x][l][r]) return f[x][l][r];
	if(l==r) return f[x][l][r]=C[l];
	if(l>r) return 1;
	int res = 0 ;
	if(l==x)//边界
	{
		for(int j=x+1;j<=r;j++)
		{
			if(dp(j,x+1,r)>res)
			{
				res = dp(j,x+1,r) ;
				rt[x+1][r] = j ;
			} 
		} 
	}
	for(int i=l;i<x;i++)
	{
		for(int j=x+1;j<=r;j++)
		{
			if( dp(i,l,x-1) * dp(j,x+1,r) > res )
			{
				res = dp(i,l,x-1) * dp(j,x+1,r) ;
				rt[l][x-1] = i ;
				rt[x+1][r] = j ;
			} 
		}
		if(x==r) //边界
		{
			if( dp(i,l,x-1) > res )
			{ 
				res = dp(i,l,x-1) ;
				rt[l][x-1] = i ;
			} 
		}
	}
	return f[x][l][r] = res + C[x] ;
}
void GetPath(int l,int r)
{ 
	if(l==r) 
	{
		P.push_back(l);
		return ;
	}
	int x = rt[l][r] ;
	P.push_back(x);
	if(x>l) GetPath(l,x-1);
	if(x<r) GetPath(x+1,r);
	return ;
}
signed main()
{    
	scanf("%lld",&n);
	for(int i=1;i<=n;i++) scanf("%lld",C+i);
	for(int i=1;i<=n;i++)
	{
		if(dp(i,1,n)>ans)
		{
			rt[1][n]=i;
			ans= dp(i,1,n) ; 
			P.clear();
			GetPath(1,n);
		} 
	} 
	printf("%lld\n",ans);
	for(auto x:P) printf("%lld ",x);
}

我认为状态数为n^3 而记搜保证了只会看一遍
所以是n^3吗（
还是转移乘上状态数最后是n^5捏