题见洛谷
#include<iostream>#include<cstdio>#include<cstring>#include<string> #include<algorithm>using namespace std;long long ans=0;int a[300],n,f[300][300];int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); a[i+n]=a[i];//复制为2倍长的线，化环为线，区间dp } for(int p=1;p<=n-1;p++) for(int i=1;i<=2*n-p;i++) { int j=i+p; for(int k=i;k<=j-1;k++) f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]+a[i]*a[k+1]*a[j+1]); } int maxn=-10; for(int i=1;i<=n;i++) { if(f[i][i+n-1]>maxn) maxn=f[i][i+n-1]; } PRintf("%d",maxn); return 0;}新闻热点
疑难解答
