2016-05-31 20:48:47

题目链接:

题目大意:

　　一个贼要在一个二叉树结构的艺术馆中偷画,画都处于叶子节点处,偷画和经过走廊都需要时间,求在限定时间内可以偷到最大数量

解法:

　　树状DP (记忆化搜索实现)

　　DP[i][j]表示到达i节点时还有j的时间来移动可以偷到的最大数量

　　状态转移:

　　　　对于叶子节点,直接按时间剩余返回最大偷画数量　　

　　　　对于非叶子节点,最大值可能来自Lson一边,也可能只来自Rson一边,还有可能是Lson,Rson按某种方式分配时间得来

　　话说这题按照深度优先顺序给树有点坑啊

需要注意的地方:

　　1.偷画是要有来有回的,所以要把走廊的长度*2

　　2.第一条走廊并不满足二叉结构,可以直接手动去掉

1 //访问艺术馆 (Codevs No.1163) 2 //树状DP 3 #include
     
       4 #include
      
        5 #include
       
         6 using namespace std; 7 const int maxn=110; 8 const int maxt=610; 9 int DP[maxn][maxt];10 int T;11 int Index=1;12 int val[maxn];13 int lson[maxn];14 int rson[maxn];15 int lenlson[maxn];16 int lenrson[maxn];17 void Build(int now)18 {19     int len,num;20     scanf("%d %d",&len,&num);21     lson[now]=++Index;22     lenlson[now]=len*2;23     if(num==0)Build(lson[now]);24     else val[lson[now]]=num;25     scanf("%d %d",&len,&num);26     rson[now]=++Index;27     lenrson[now]=len*2;28     if(num==0)Build(rson[now]);29     else val[rson[now]]=num;30     return ;31 }32 int DFS(int x,int time)33 {34     if(time<0)return -100000;35     if(DP[x][time]>-1)return DP[x][time];36     if(lson[x]==0&&rson[x]==0)37     {38         for(int i=val[x];i>=0;i--)39         {40             if(time-i*5>=0)return DP[x][time]=i;41         }42     }43     DP[x][time]=0;44     DP[x][time]=max(DP[x][time],DFS(lson[x],time-lenlson[x]));45     DP[x][time]=max(DP[x][time],DFS(rson[x],time-lenrson[x]));46     for(int i=lenlson[x];time-i>=lenrson[x];i++)47     {48         DP[x][time]=max(DP[x][time],DFS(lson[x],i-lenlson[x])+DFS(rson[x],time-i-lenrson[x]));49     }50     return DP[x][time];51 }52 int main()53 {54     int x,y;55     scanf("%d",&T);56     scanf("%d %d",&x,&y);57     if(y==0)58     {59         Build(1);60     }61     memset(DP,-1,sizeof(DP));62     DFS(1,T-x*2-1);63     if(T-x*2-1>=0)printf("%d",DP[1][T-x*2-1]);64     else printf("0");65     return 0;66 }