solution

1.记搜
mem[i][j]表示a[i]到a[j]的最大值


code:

#include<bits/stdc++.h>
using namespace std;
const int N=20;
int t,n,a[N],mem[N][N];
int dfs(int l,int r){
	if(mem[l][r]!=-1) return mem[l][r];//若以出现则无循环的必要
	if(l==r) return a[l];
	int ans=0;
	for(int i=l;i<r;i++){此循环相当于把l到i打括号，i+1到r打括号，所以在循环内处理乘法和加法
		ans=max(ans,max(dfs(l,i)*dfs(i+1,r),dfs(l,i)+dfs(i+1,r)));//俩者取优
	}
	return mem[l][r]=ans;//记忆
}
int main(){
	cin>>t;
	while(t--){
		cin>>n;
		memset(mem,-1,sizeof(mem));
		for(int i=1;i<=n;i++) cin>>a[i];
		cout<<dfs(1,n)<<"\n";
	}
	return 0;
}
2.dp
此题为区间dp,那么可以将方程f[i][j]设为a[i]到a[j]的最大值
所以f[i][i]为a[i],以此基准进行dp,方程为f[i][j]=
for(int i=l;i<r;i++){
	f[l][r]=max(f[l][r],max(f[l][i]*f[i+1][r],f[l][i]+f[i+1][r]));
}
与记搜相似


code:

#include<bits/stdc++.h>
using namespace std;
const int N=20;
int t,n,a[N],f[N][N];
int main(){
	cin>>t;
	while(t--){
		cin>>n;
		memset(f,0,sizeof(f));
		for(int i=1;i<=n;i++) cin>>a[i];
		for(int i=1;i<=n;i++) f[i][i]=a[i];
		for(int len=2;len<=n;len++){//区间长度
			for(int l=1,r=len;r<=n;l++,r++){//设立左端点和右端点
				for(int i=l;i<r;i++){
					f[l][r]=max(f[l][r],max(f[l][i]*f[i+1][r],f[l][i]+f[i+1][r]));//方程
				}
			}
		}
		cout<<f[1][n]<<"\n";//最后答案为a[1]到a[n]的最长长度
	}
	return 0;
}