CodeVS 1154 Noip2006 能量项链 【DP】

tonyfang posted @ 2015年9月18日 22:12 in codevs with tags c++ OI , 333 阅读

和前几题类似,但是要用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;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter