#include <bits/stdc++.h> using namespace std; const int N = 55, M = 35; int n; int w[N]; int dp[N][N][M]; void add(int a[],int b[]){ int t=0; for(int i=0;i<M;i++){ t+=a[i]+b[i]; a[i]=t%10; t/=10; } } void mul(int a[],int b){ long long t=0; for(int i=0;i<M;i++){ t+=1ll*a[i]*b; a[i]=t%10; t/=10; } } int cmp(int a[],int b[]){ for(int i=M-1;i>=0;i--){ if(a[i]>b[i])return 1; else if(a[i]<b[i])return -1; } return 0; } void print(int a[]){ int k=M-1; while(k&&!a[k])k--; while(k>=0)cout<<a[k--]; } int main() { ios::sync_with_stdio(false); cin>>n; for(int i=1;i<=n;i++)cin>>w[i]; int temp[M]; for(int len=3;len<=n;len++){ for(int j=1;j+len<=n+1;j++){ int ends=j+len-1; dp[j][ends][M-1]=1; for(int i=j+1;i<ends;i++){ memset(temp,0,sizeof temp); temp[0]=1; mul(temp,w[j]); mul(temp,w[i]); mul(temp,w[ends]); add(temp,dp[j][i]); add(temp,dp[i][ends]); if(cmp(dp[j][ends],temp)>0) memcpy(dp[j][ends],temp,sizeof temp); } } } print(dp[1][n]); return 0; }
原文:https://www.cnblogs.com/qq1415584788/p/14788449.html