区间DP 不多说了 和上面那个题一样
还是日常DFS写DP 不会循环
#include<bits/stdc++.h> #define fi first #define se second #define io std::ios::sync_with_stdio(false) using namespace std; typedef long long ll; typedef pair<int,int> pii; const int P = 1e9+7, INF = 0x3f3f3f3f; ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} ll qpow(ll a,ll n){ll r=1%P;for (a%=P; n; a=a*a%P,n>>=1)if(n&1)r=r*a%P;return r;} int f[1005][2005]; int a[1005]; int dfs(int l,int r) { if(l==r) return 0; if(f[l][r]) return f[l][r]; int ans=0; for(int i=l;i<r;i++) { ans=max(dfs(l,i)+dfs(i+1,r)+a[l]*a[i+1]*a[r+1],ans); } return f[l][r]=ans; } int main() { int n; cin>>n; memset(f,0,sizeof(f)); for(int i=1;i<=n;i++) { cin>>a[i]; a[i+n]=a[i]; } a[n+1]=a[1]; int ans=0; for(int i=1;i<=n;i++) ans=max(ans,dfs(i,i+n-1)); cout<<ans<<endl; }