Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:赞一个...话说不懂转化成二叉树有多大好处...

Posted by wzc1989 at 2009-10-14 21:06:31 on Problem 2486
In Reply To:为了这道题贡献了32个WA啊。。。。给大家一点提示 Posted by:forsona at 2009-03-05 22:46:37
> 不知怎么,这么一道简单的TreeDP弄得我这么狼狈。。。
> 关于这道题,网上有两种解法,一种是双DP,过程叫清楚,也适合于对于TreeDP不是太了解或者自由树转有根树理解不太透彻的人来做,抑或对背包问题了解的很牛的人,过双DP也很简单。。其实双DP也很具有启发意义,是很精巧的算法。。。但是个人认为第二种算法更体现了TreeDP的精髓。。
> 这儿介绍一下第二种方法
> 
> 先把自由树转化成有根树(直接转成孩子兄弟表示法),网上我找到的唯一一个用这种方法做的人,在树的转化这个环节用了100行(Orz,膜拜),其实一个遍历就可以了。孩子兄弟表示法到处都有教程,这儿就不多赘述)
> 
> void Zh(int p)
> {
>   f[p]=1;
>   for(int i=0;i<d[p];i++)
>     if (!f[next[p][i]])      
>       {
>       bro[next[p][i]]=son[p];
>       son[p]=next[p][i];
>       Zh(next[p][i]);                       
>       }
> }
> 
> 然后直接TreeDP
> 用maxt[0][p][m]表示p的右边兄弟和下面儿子(这个有点XX吧,但是相信大家能理解)消耗m步还要回起点p,最多能吃的个数。。
> 用maxt[1][p][m]表示p的右边兄弟和下面儿子,消耗m步不需回起点p,最多能吃的个数。。
> 
> 对于每一个节点p,先考虑无视p的情况(p取不到),直接把“走路的权利”传给自己右边兄弟的情况。
> 接下来我们考虑的情况,p一定能取道。
> 分“只往下扩展孩子”和“只往右扩展兄弟”两种情况。
> 最后,考虑既扩展孩子又扩展兄弟的情况。。。
> 
> 其中最复杂的就算是“走路的权利”的问题了。。。
> 我们分maxt[0]和maxt[1]两种情况讨论
> 
> maxt[0]时,一定要回到原点,那么很简单,扩展孩子和扩展右边兄弟的时候,“走路的权利”都要-2(想想为什么?)
> 
> maxt[0]时,不需要回到原点,那么扩展右边兄弟的时候,“走路的权利”-2,而扩展孩子的时候,只需要-1(想想为什么?)
> 
> 这两个问题,如果你画一下图,也许能很快明白。。。。
> 
> 如果你全部明白了,恭喜你,这道题AC将会在30分钟内诞生。。。
> 
> 祝你成功!
> 
> 
> PS:
>     以下是小弟的代码,为了看的清楚,我把程序写的简洁,但也损失了很多时间,当然对于p==0和m==0的时候的剪枝,其实很可以做的更好。
>      祝大家AC愉快!
> 
> Source Code
> 
> Problem: 2486  User: forsona 
> Memory: 620K  Time: 422MS 
> Language: G++  Result: Accepted 
> 
> Source Code 
> #include"iostream"
> #define INF -99999999
> using namespace std;
> int d[110],next[110][110],son[110],bro[110],c[110],f[110],n,k,maxt[2][110][210],r;
> void Zh(int p)
> {
>   f[p]=1;
>   for(int i=0;i<d[p];i++)
>     if (!f[next[p][i]])      
>       {
>       bro[next[p][i]]=son[p];
>       son[p]=next[p][i];
>       Zh(next[p][i]);                       
>       }
>   memset(maxt,-1,sizeof(maxt));      
> }
> void Inp(void)
> {
>   int i,j,k;
>   memset(d,0,sizeof(d));
>   for(i=1;i<=n;i++)
>     scanf("%d",&c[i]);
>   for(i=0;i<n-1;i++)
>     {
>     scanf("%d%d",&j,&k);
>     next[j][d[j]++]=k;
>     next[k][d[k]++]=j;
>     } 
>   memset(bro,0,sizeof(bro));
>   memset(son,0,sizeof(son));    
>   memset(f,0,sizeof(f));  
>   Zh(1);
>   
> }
> int Loop(int b,int p,int m)                          
>  //b==0  back to root     b==1  no need to root
> {
>   int i,mt;
>   if (maxt[b][p][m]!=-1)
>     return maxt[b][p][m];
>   if (!p)
>     return maxt[b][p][m]=0;  
>   if (m==0)
>     return maxt[b][p][m]=max(Loop(b,bro[p],m),c[p]);  
>   if (b==0)
>     {
>     mt=Loop(0,bro[p],m);
>     if (m>=2)
>       {
>       mt=max(mt,c[p]+Loop(0,bro[p],m-2));
>       mt=max(mt,c[p]+Loop(0,son[p],m-2));
>       }
>     for(i=0;i<=m-4;i++)  
>       mt=max(mt,Loop(0,bro[p],i)+Loop(0,son[p],m-4-i)+c[p]);
>     return maxt[b][p][m]=mt;        
>     }
>   else
>     {
>     mt=Loop(1,bro[p],m);       
>     mt=max(mt,c[p]+Loop(1,son[p],m-1));
>     if (m>=2)
>       mt=max(mt,c[p]+Loop(1,bro[p],m-2));
>     for(i=0;i<=m-4;i++)
>       mt=max(mt,Loop(1,bro[p],i)+Loop(0,son[p],m-4-i)+c[p]); 
>     for(i=0;i<=m-3;i++)         
>       mt=max(mt,Loop(0,bro[p],i)+Loop(1,son[p],m-3-i)+c[p]);          
>     return maxt[b][p][m]=mt;       
>     }  
> }
> int main()
> {
>   while(scanf("%d%d",&n,&k)!=EOF)
>     {
>     Inp();
>     r=Loop(1,1,k);
>     printf("%d\n",r);                             
>     }
>   return 0;  
> } 
> 

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator