AcWing 1068. 环形石子合并 - AcWing
#include<iostream>
#define INF 0x3f3f3f3f
#define inf 0xc0c0c0c0
using namespace std;
#include<cstring>
int f[410][410];
int g[410][410];
int a[410];
int s[410];int main(){int n;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];a[i+n]=a[i];}for(int i=1;i<=2*n;i++){s[i]=s[i-1]+a[i];}memset(f,0x3f,sizeof(f));memset(g,0xc0,sizeof(g));for(int len=1;len<=n;len++){for(int i=1;i+len-1<=n*2;i++){int j=i+len-1;if(len==1)f[i][j]=g[i][j]=0;for(int k=i;k<=j-1;k++){f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]);g[i][j]=max(g[i][j],g[i][k]+g[k+1][j]+s[j]-s[i-1]);}}}int ans1=INF;int ans2=inf;for(int i=1;i<=n;i++){ans1=min(ans1,f[i][i+n-1]);ans2=max(ans2,g[i][i+n-1]);}cout<<ans1<<endl<<ans2;
}
AcWing 320. 能量项链 - AcWing
#include<iostream>
using namespace std;int a[210];
int f[210][210];int main(){int n;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];a[i+n]=a[i];}for(int len=3;len<=n+1;len++){for(int i=1;i+len-1<=2*n;i++){int j=i+len-1;for(int k=i+1;k<=j-1;k++){f[i][j]=max(f[i][j],f[i][k]+f[k][j]+a[i]*a[k]*a[j]);}}}int ans=0;for(int i=1;i<=n;i++){ans=max(ans,f[i][i+n]);}cout<<ans;}
