|
传送门
由于可以后面接在前面,我们将整个项链复制一倍,再在新的项链上找一个最大
区间DP一般以len(区间长)从小到大开始更新 , 所以第一维要枚举len
f[i][j]表示将i--j合并为一个点的最大价值
![f[i][j] = max(f[i][j] , f[i][k-1] + f[k][j] + a[i]*a[k]*a[j+1]);](https://201907.oss-cn-shanghai.aliyuncs.com/cs/5606289-3a94361a520e6a244ced93056924ab8e.latex)
#include<bits/stdc++.h>
#define N 150*2
using namespace std;
int f[N][N],n,a[N],ans;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]); a[i+n] = a[i];
}
for(int len=2;len<=n;len++)
for(int i=1;i<=n*2-len+1;i++)
for(int k=i+1;k<i+len;k++){
int j=i+len-1;
f[i][j] = max(f[i][j] , f[i][k-1] + f[k][j] + a[i]*a[k]*a[j+1]);
}
for(int i=1;i<=n;i++) ans = max(ans , f[i][i+n-1]);
printf("%d",ans); return 0;
}
| 
转播
