AcWing 320. 能量项链
原题链接
中等
作者:
最后五分钟
,
2024-03-29 16:51:44
,
所有人可见
,
阅读 7
#include<bits/stdc++.h>
#define int long long
#define x first
#define y second
#define de(x) cout<<#x<<" = "<<x<<" "
#define deg(x) cout<<#x<<" = "<<x<<endl
using namespace std;
const int N=210;
typedef pair<int,int> PII;
int f[N][N],a[N];
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=n+1;i<=2*n;i++)a[i]=a[i-n];
for(int len=1;len<=n;len++)
for(int l=1;l+len-1<2*n;l++)
{
int r=l+len-1;
for(int k=l;k<r;k++){
f[l][r]=max(f[l][r],f[l][k]+f[k+1][r]+a[l]*a[k+1]*a[r+1]);
}
}
int res=0;
for(int l=1;l<=n;l++)
res=max(res,f[l][l+n-1]);
cout<<res<<endl;
return 0;
}
请问这个题是因为不满足单调性从而不能进行四边形优化吗?