访问美术馆AC代码

#include<bits/stdc++.h>
using namespace std;
int f[205][605],t[205],v[205];// f[i][j],i个点 j是剩下时间
void build(int x)
{
	cin>>t[x]>>v[x];
	t[x]*=2;// 要出去，走两会
	if(v[x]==0)
	{
	build(x<<1);
	build((x<<1)+1);	
	}
}
int dfs(int x,int time) // 第x个点（第i个走廊末端） ， 剩余time  return f[x][time];
{	
      if(time<=0) return 0;
	 if(f[x][time]!=0) return f[x][time];
	 if(v[x]==0){  // 岔路
	   int y=x<<1;			             
	 for(int i=0;i<=time;i++) { // left left son i// left right is time-i 
	    int mid=dfs(y,i-t[y])+dfs(y+1,time-i-t[1+y]);// 表示走廊末端，-t[y],-t[y+1]
	    f[x][time]=max(f[x][time],mid);	
	      }
	 }
	 else                                   // 到了画室 t[2*x],t[2*x+1]==0
	  return  f[x][time]=min(v[x],(time)/5);//小贪心,不偷玩不换地偷，除了时间不够了，撤离
	return f[x][time];
}
int main()
{  
    int time;
	cin>>time;
	time-=1;
	build(1);
	time-=t[1];
	cout<<dfs(1,time);
	return 0;
}

偷天换日样例不过代码

#include<bits/stdc++.h>
using namespace std;
int f[10005][605],t[10005],v[10005];// f[i][j],i个点 j是剩下时间
vector<int> w[10005],c[10005];
void build(int x)
{
	cin>>t[x]>>v[x];
	t[x]*=2;// 要出去，走两会
	int wi,ci;
	for(int i=1;i<=v[x];i++){
	cin>>wi>>ci;
	w[x].push_back(wi);	
	c[x].push_back(ci);
	}
	if(v[x]==0)
	{
	build(x<<1);
	build((x<<1)+1);	
	}
}
int dfs(int x,int time) // 第x个点（第i个走廊末端） ， 剩余time  return f[x][time];
{	
      if(time<=0) return 0;
	 if(f[x][time]!=0) return f[x][time];
	 if(v[x]==0){  // 岔路
	   int y=x<<1;			             
	 for(int i=0;i<=time;i++) { // left left son i// left right is time-i 
	    int mid=dfs(y,i-t[y])+dfs(y+1,time-i-t[1+y]);// 表示走廊末端，-t[y],-t[y+1]
	    f[x][time]=max(f[x][time],mid);	
	      }
	 }
	 else                                        // 到了画室 t[2*x],t[2*x+1]==0
	  {       
	    for(int i=0;i<v[x];i++)
	    for(int j=time;j>=c[x][i];j--)
	    f[x][j]=max(f[x][j],f[x][j-c[x][i]]+w[x][i]);
	    return f[x][time];
	  }    
	return f[x][time];
}
int main()
{  
    int time;
	cin>>time;
	time-=1;
	build(1);
	time-=t[1];
	cout<<dfs(1,time);
	return 0;
}
```cpp