memory2

三年前写过的一道练习题

加分二叉树 LuoguP1040

#include<bits/stdc++.h>
using namespace std;
const int N=40;  
int f[N][N];
int rt[N][N];
int v[N];	
int n;
void way(int l,int r){
	if(l>r) return ;
	cout<<rt[l][r]<<" ";
	way(l,rt[l][r]-1);
	way(rt[l][r]+1,r);
}
int main(){

	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>v[i];
		f[i][i]=v[i];
		rt[i][i]=i;	
	}
	for(int i=2;i<=n;i++){
		for(int left=1;left+i-1<=n;left++){
			int right=left+i-1;
			if(f[left][right]<v[left]+f[left+1][right]){
				f[left][right]=v[left]+f[left+1][right];
				rt[left][right]=left;
			}
			if(f[left][right]<v[right]+f[left][right-1]){
                f[left][right]=v[right]+f[left][right-1];
                rt[left][right] = right;	
            }
            for(int j=left+1;j<=right-1;j++){
                if(f[left][j-1]*f[j+1][right]+v[j] > f[left][right]){
                    f[left][right] = f[left][j-1]*f[j+1][right]+v[j];
                    rt[left][right]=j;
                }
			}
		}
	}
	cout<<f[1][n]<<endl;
	way(1,n);
	return 0;
}