C++14(g++5.4) 解法, 执行用时: 4ms, 内存消耗: 376K, 提交时间: 2019-10-24 13:36:30

#include<cstring>
#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
int dp[100][100];
int root[100][100];
int find(int l, int r) {
	ll now, ans;
	if (l > r) return 1;
	if (dp[l][r] == -1) {
		for (int i = l; i <= r; i++) {
			now = find(l, i - 1)*find(i + 1, r) + dp[i][i];
			if (now > dp[l][r]) {
				dp[l][r] = now;
				root[l][r] = i;
			}
		}
	}
	return dp[l][r];
}
int flag = 1;
int println(int l,int r) {
	if (l > r) return 0;
	if (flag) flag = 0;
	else printf(" ");
	printf("%d", root[l][r]);

	println(l, root[l][r] - 1);
	println(root[l][r] + 1, r);
}
int main() {
	int n;
	scanf("%d", &n);
	memset(dp, -1, sizeof(dp));
	for (int i = 1; i <= n; i++) {
		scanf("%d", &dp[i][i]);
		root[i][i] = i;
	}
	printf("%d\n", find(1, n));
	
	println(1, n);
	return 0;
}

C++ 解法, 执行用时: 3ms, 内存消耗: 584K, 提交时间: 2022-06-08 11:22:25

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll d[1111][1111];
ll f[1111][1111];
ll a[1111],n;
void dfs(ll l,ll r)
{
	if(l>r)return ;
	cout<<d[l][r]<<" ";
	dfs(l,d[l][r]-1);
	dfs(d[l][r]+1,r);
}
int main()
{
	scanf("%d",&n);
	for(ll i=1; i<=n; i++)
	{
		scanf("%d",&a[i]);
		f[i][i]=a[i];
		d[i][i]=i;
	}
	for(ll len=1; len<n; len++)
	for(ll i=1; i+len<=n; i++)
	{
		int j=i+len;
		for(ll k=i; k<=j; k++)
		{
			int l=f[i][k-1];
			int r=f[k+1][j];
			if(k==i)l=1;
			if(k==j)r=1;
			if(l*r+a[k]>f[i][j])
			{
				f[i][j]=l*r+a[k];
				d[i][j]=k;
			}
		}
	}
	cout<<f[1][n]<<endl;
	dfs(1,n);
	cout<<endl;
    return 0;
}