CodeVS 1154 Noip2006 能量项链 【DP】
和前几题类似，但是要用DP，不然会TLE。
# include <stdio.h>
# include <algorithm>
using namespace std;
int n, a[230], f[230][230];
inline int get() {
for (int len=1;len<n;++len) {
for (int i=1;i<=2*n-1-len;++i) {
int j=i+len;
for (int k=i;k<j;++k)
f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]+a[i-1]*a[j]*a[k]);
}
}
int ans=0;
for (int i=1;i<=n;++i) ans=max(ans,f[i][i+n-1]);
return ans;
}
main() {
scanf("%d",&n);
for (int i=0;i<n;++i) scanf("%d",&a[i]);
for (int i=n;i<2*n;++i) a[i]=a[i-n];
//printf("%d\n",get(1,n));
printf("%d\n",get());
return 0;
}
2023年4月15日 22:39
We are Proficinal Bloggers and we have Published the Blog/ Website to Support Better Education that’s way we have provide this information to help JNVST 2019 Students, and every student can please note we are not responsible, if Any mistakes in the Content or Information, and we are not officials https://navodayaresult2019.com/ of the Jawahar Navodaya Vidhyalaya Samiti, We have Provided the Information Only for reference Purpose and we are not responsible to any errors and mistakes in the provided information.