社区讨论
如何是多叉树怎么写?
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 条回复,欢迎继续交流。
正在加载回复...