【洛谷3360】偷天换日

题面

题目背景

神偷对艺术馆内的名画垂涎欲滴准备大捞一把。

题目描述

艺术馆由若干个展览厅和若干条走廊组成。每一条走廊的尽头不是通向一个展览厅，就

是分为两个走廊。每个展览厅内都有若干幅画，每副画都有一个价值。经过走廊和偷画都是

要耗费时间的。

警察会在n 秒后到达进口，在不被逮捕的情况下你最多能得到的价值。

输入格式：

第一行一个整数 n(n≤600)。

第二行若干组整数，对于每组整数（t,x），t 表示进入这个展览厅或经过走廊要耗费 t秒的时间，若x>0 表示走廊通向的展览厅内有x 幅画,接下来x对整数(w,c)表示偷一幅价值为 w 的画需要 c秒的时间。若x=0 表示走廊一分为二。(t，c≤5; x≤30)

输入是按深度优先给出的。房间和走廊数不超过 300 个。

输出格式：

仅一个整数，表示能获得的最大价值。

输入样例#1：

50
5 0 10 1 10 1 5 0 10 2 500 1 1000 2 18 1 1000000 4

输出样例#1：

1500

题解

这道题和洛谷上的另外一道题目几乎一样

读入的方式相同，采用递归读入的方式。
而树上的DP由原来的固定时间、价值更改为给定的时间和价值
那么，转换为01背包来做即可。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
#define MAX 1000
inline int read()
{
	  register int x=0,t=1;
	  register char ch=getchar();
	  while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
	  if(ch=='-'){t=-1;ch=getchar();}
	  while(ch<='9'&&ch>='0'){x=x*10+ch-48;ch=getchar();}
	  return x*t;
}
struct Pic//画的信息 
{
	  int v;//价值 
	  int t;//时间 
};
vector<Pic> P[MAX];//存放画的信息  
struct Line
{
	  int v,next,w;
}e[MAX];
int h[MAX],tot=1,cnt;
int T,Ans;
int f[MAX][MAX];
int le[MAX];
inline void Add(int u,int v,int w)
{
	  e[tot]=(Line){v,h[u],w};
	  h[u]=tot++;
}
void get(int ff)
{
	  int w=read()*2,v=read();
	  Add(ff,++cnt,w);
	  if(!v)//分出走廊 
	  {
	  	     int now=cnt;
			 get(now);
			 get(now); 
	  }
	  else//读入画的信息
	  {
	  	     le[cnt]=v;
	  	     for(int i=1;i<=v;++i)
	  	        P[cnt].push_back((Pic){read(),read()});
      }
}
void DFS(int u)
{
	  if(le[u])//是叶子节点
	  {
	  	     for(int i=0;i<le[u];++i)//枚举所有画
	  	     {
	  	     	    for(int j=T-1;j>=P[u][i].t;--j)//枚举时间 
						    f[u][j]=max(f[u][j],f[u][j-P[u][i].t]+P[u][i].v);
	  	     }
	  	     return;
	  }
	  for(int i=h[u];i;i=e[i].next)
	  {
	  	    int v=e[i].v;
	  	    DFS(v);
	  	    for(int j=T-1;j;--j)//枚举时间 
	  	    {
	  	    	    for(int k=0;k<T;++k)//枚举分配的时间 
	  	    	    	 if(j>=k+e[i].w)
	  	    	    	    f[u][j]=max(f[u][j],f[u][j-k-e[i].w]+f[v][k]);
	  	    }
	  }
	  
}
int main()
{
	  T=read();
	  get(0);
	  DFS(0);
	  for(int i=1;i<T;++i)
         Ans=max(Ans,f[0][i]);
      cout<<Ans<<endl;
      return 0;
}