社区讨论

如何是多叉树怎么写?

P1270“访问”美术馆参与者 2已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@lod09eoz
此快照首次捕获于
2023/10/30 22:38
2 年前
此快照最后确认于
2023/11/05 08:56
2 年前
查看原帖
RT,我按照树上背包的板子,只是将f[][]换成了dfs( , ),就TLE了。求大佬解释 =.=
CPP
#include <iostream>
#include <cstdio>
using namespace std;

const int N=3005;

struct E {int nex,to;} e[N];
int T,n,num;
int h[N],a[N],b[N];
int rem[N][N];

void add(int u,int v) {e[++num]={h[u],v},h[u]=num;}
void init(int x) {
	int t,op; scanf("%d%d",&t,&op),t*=2;
	if(!op) {
		a[x]=t;
		add(x,++n),init(n);
		add(x,++n),init(n);
	}
	else a[x]=t,b[x]=op;
}

int dfs(int x,int tim) {
	
	if(tim<5) return 0; 
	if(rem[x][tim]) return rem[x][tim];
	if(!h[x]) {
		int cnt=(tim-a[x])/5;
		return rem[x][tim]=min(cnt,b[x]);
	}
	int ans=0;
	for(int i=h[x];i;i=e[i].nex) {
		int y=e[i].to;
		for(int j=tim-a[x];j>=a[y];j--)
			for(int l=a[y];l<=j;l++)
				ans=max(ans,dfs(y,l)+dfs(x,tim-l));
	}
	return rem[x][tim]=ans;
	/*二叉树写法,可A
	int ans=0,y1=e[h[x]].to,y2=e[e[h[x]].nex].to;
	for(int i=tim-a[x];i>=0;i--)
		ans=max(ans,dfs(y1,i)+dfs(y2,tim-a[x]-i));
	return rem[x][tim]=ans;
	*/
}

int main()
{
	freopen("P1270.in", "r", stdin);
	freopen("P1270.out", "w", stdout);
	
	cin>>T,T--,init(++n);
	cout<<dfs(1,T);
	return 0;
}

回复

1 条回复,欢迎继续交流。

正在加载回复...