CodeVS 1090 加分二叉树 【动态规划/记忆化搜索】

tonyfang posted @ 2015年9月18日 21:50 in codevs with tags c++ OI , 292 阅读

和上题一样,不过在记忆化过程中记录下根是谁即可。

 

# include <stdio.h>
using namespace std;
bool v[55][55];
# define LBW int
LBW f[55][55], a[55];
LBW root[55][55], n;
inline int get(int l,int r) {
	if (l>r) return 1;
	if (v[l][r]) return f[l][r];
	int ans=0; v[l][r]=1;
	for (int i=l;i<=r;++i) {
		int now=get(l,i-1)*get(i+1,r)+a[i];
		if(now>ans) ans=now,root[l][r]=i;
	}
	return f[l][r]=ans;
}
inline void put(int l,int r) {
	int now = root[l][r];
	printf("%d ", now);
	if(l<now) put(l,now-1);
	if(r>now) put(now+1,r);
}
main() {
	scanf("%d",&n);
	for (int i=1;i<=n;++i) scanf("%d",&a[i]);
	for (int i=1;i<=n;++i) root[i][i]=i,f[i][i]=a[i],v[i][i]=1;
	printf("%d\n",get(1,n));
	put(1,n);
	return 0;
}

登录 *


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