3252 - 偷天换日
神偷对艺术馆内的名画垂涎欲滴准备大捞一把。艺术馆由若干个展览厅和若干条走廊组成。每一条走廊的尽头不是通向一个展览厅，就是分为两个走廊。每个展览厅内都有若干幅画，每副画都有一个价值。经过走廊和偷画都是要耗费时间的。警察会在第n秒到达进口，在不被逮捕的情况下你最多能得到的价值。
题目输入
第一行一个整数 n
第二行若干组整数，对于每组整数（t,x），t表示进入这个展览厅或经过走廊要耗费t秒的时间，若x>0表示走廊通向的展览厅内有x幅画,接下来x对整数(w,c)表示偷一幅价值为w的画需要c秒的时间。若x=0表示走廊一分为二。
输入是按深度优先给出的。
题目输出
仅一个整数，表示能获得的最大价值。
输入/输出样例
题目输入
50 5 0 10 1 10 1 5 0 10 2 500 1 1000 2 18 1 1000000 4
题目输出
1500
提示
Hint
n≤600；t，c≤5；x≤30
房间和走廊数不超过300个。
注意题目要求你在的情况下得到最多的价值 不被逮捕样例的输入对应于下图<img src="http://tk.hustoj.com:80/attached/image/20141017/20141017112948_50179.png" alt="" />
C++解答
#include<iostream> #include<cstring> #include<cstdio> using namespace std; int n,m,v,x,y,k,l,num; int a[301][3]; int f[301][601]; int t[301]; int m_max(int x,int y) { if(x>y) return x; else return y; } void init(int); void treedp(int); int main() { //freopen("steal.in","r",stdin); //freopen("steal111.out","w",stdout); cin>>v; num=1; init(1); treedp(1); cout<<f[1][v-1]<<endl; return 0; } void init(int now) { cin>>t[now]>>k; if(k==0) { num++; a[now][1]=num; init(num); num++; a[now][2]=num; init(num); } else { for(int i=1;i<=k;i++) { cin>>x>>y; for(int j=v;j>=t[now]+t[now]+y;j--) { f[now][j]=max(f[now][j],f[now][j-y]+x); // cout<<"f["<<now<<"]["<<j<<"]="<<f[now][j]<<' '; } //cout<<endl; } } } void treedp(int now) { if(a[now][1]+a[now][2]==0) return; treedp(a[now][1]); treedp(a[now][2]); for(int i=0;i<=v;i++) for(int j=i-t[now]-t[now];j>=0;j--) f[now][i]=max(f[now][i],f[a[now][1]][j]+f[a[now][2]][i-j-t[now]-t[now]]); }
提示
Hint
n≤600；t，c≤5；x≤30
房间和走廊数不超过300个。
注意题目要求你在的情况下得到最多的价值 不被逮捕
样例的输入对应于下图
<img src="http://tk.hustoj.com:80/attached/image/20141017/20141017112948_50179.png" alt="" />