【洛谷1270】“通路”美術館

題目描述

經過數月的精心準備，Clever·YL，一個出了名的盜畫者，準備開始他的下一個行動。藝術館的結構，每條走廊要麼分叉為兩條走廊，要麼通向一個展覽室。YL知道每個展室裡藏畫的數量，并且他精确測量了通過每條走廊的時間。由于經驗老到，他拿下一幅畫需要5秒的時間。你的任務是編一個程式，計算在警察趕來之前，他最多能偷到多少幅畫。

輸入格式：

第1行是警察趕到的時間，以s為機關。第2行描述了藝術館的結構，是一串非負整數，成對地出現：每一對的第一個數是走過一條走廊的時間，第2個數是它末端的藏畫數量；如果第2個數是0，那麼說明這條走廊分叉為兩條另外的走廊。資料按照深度優先的次序給出，請看樣例。

一個展室最多有20幅畫。通過每個走廊的時間不超過20s。藝術館最多有100個展室。警察趕到的時間在10min以内。

輸出格式：

輸出偷到的畫的數量

輸入樣例#1：

60

7 0 8 0 3 1 14 2 10 0 12 4 6 2

輸出樣例#1：

2

題解

樹形DP

這題有兩個難點

第一個是如何讀入資料

這裡使用的是遞歸讀入并建樹

另外考慮DP

至于要考慮如何配置設定時間即可

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define MAX 2000
inline int read()
{
      register int x=,t=;
      register char ch=getchar();
      while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
      if(ch=='-'){t=-;ch=getchar();}
      while(ch<='9'&&ch>='0'){x=x*+ch-;ch=getchar();}
      return x*t;
}
struct Line
{
      int v,next,w;
}e[MAX*];
int h[MAX],tot=;
int cnt,w,v,le[MAX];
int f[MAX][];
int T;
inline void Add(int u,int v,int w)
{
      e[tot]=(Line){v,h[u],w};
      h[u]=tot++;
}
void Get(int ff)
{
      register int w=*read();//權值直接乘2，不用再考慮出去的問題 
      register int v=read();
      Add(ff,++cnt,w);
      if(v==)
      {
           int now=cnt;
           Get(now);
           Get(now);
      }
      else
           le[cnt]=v;//标記葉子節點
}
//f[i][j]表示目前節點i用j時間能夠拿走的最多的畫的數量 
void DFS(int u,int ff)//求解
{
      if(le[u])//是葉子節點
      {
             for(int i=;i<=min(le[u]*,T-);++i)
                 f[u][i]=i/;
             return;
      }
      for(int i=h[u];i;i=e[i].next)
      {
             int v=e[i].v;
             if(v!=ff)
             {
                  DFS(v,u);
                  for(int j=T-;j;--j)
                   for(int k=;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();//遞歸讀入
      DFS(,);
      int Ans=;
      for(int i=;i<T;++i)
        Ans=max(Ans,f[][i]);
      cout<<Ans<<endl;
      return ;
}