随笔 - 87  文章 - 279  trackbacks - 0
<2024年11月>
272829303112
3456789
10111213141516
17181920212223
24252627282930
1234567

潜心看书研究!

常用链接

留言簿(19)

随笔分类(81)

文章分类(89)

相册

ACM OJ

My friends

搜索

  •  

积分与排名

  • 积分 - 214327
  • 排名 - 116

最新评论

阅读排行榜

评论排行榜

Apple Tree
Time Limit:1000MS  Memory Limit:65536K
Total Submit:541 Accepted:148

Description
Wshxzt is a lovely girl. She likes apple very much. One day HX takes her to an apple tree. There are N nodes in the tree. Each node has an amount of apples. Wshxzt starts her happy trip at one node. She can eat up all the apples in the nodes she reaches. HX is a kind guy. He knows that eating too many can make the lovely girl become fat. So he doesn’t allow Wshxzt to go more than K steps in the tree. It costs one step when she goes from one node to another adjacent node. Wshxzt likes apple very much. So she wants to eat as many as she can. Can you tell how many apples she can eat in at most K steps.

Input
There are several test cases in the input
Each test case contains three parts.
The first part is two numbers N K, whose meanings we have talked about just now. We denote the nodes by 1 2 ... N. Since it is a tree, each node can reach any other in only one route. (1<=N<=100, 0<=K<=200)
The second part contains N integers (All integers are nonnegative and not bigger than 1000). The ith number is the amount of apples in Node i.
The third part contains N-1 line. There are two numbers A,B in each line, meaning that Node A and Node B are adjacent.
Input will be ended by the end of file.

Note: Wshxzt starts at Node 1.

Output
For each test case, output the maximal numbers of apples Wshxzt can eat at a line.

Sample Input

2 1 
0 11
1 2
3 2
0 1 2
1 2
1 3

Sample Output

11
2

Source
POJ Contest,Author:magicpig@ZSU


#include  < iostream >
using namespace std;

const   int  N  =   210 ;

int  adj[N][N];
int  n, k;
int  w[N];
int  go[N][N], bk[N][N];

void  solve();
void  dfs( int int );
void  dp( int int );
inline 
int  max( int  a,  int  b)  {
    
return  a  >  b  ?  a : b;
}


int  main()
{
    
while  (scanf( " %d%d " & n,  & k)  !=  EOF)  {
        solve();
    }

    
return   0 ;
}


void  solve()  {
    
int  i, j, l;
    
int  x, y;

    
for  (i = 1 ; i <= n; i ++ {
        scanf(
" %d " & w[i]);
        adj[i][
0 =   0 ;
    }


    
for  (i = 0 ; i < n - 1 ; i ++ {
        scanf(
" %d%d " & x,  & y);
        adj[x][
++ adj[x][ 0 ]]  =  y;
        adj[y][
++ adj[y][ 0 ]]  =  x;
    }

    
    memset(go, 
0 , sizeof(go));
    memset(bk, 
0 , sizeof(bk));

    dfs(
1 0 );

    
int  ans  =  max(go[ 1 ][k], bk[ 1 ][k]);
    printf(
" %d\n " , ans  +  w[ 1 ]);
}


void  dfs( int  p,  int  pp)  {
    
int  i, j, l;
    
int  ts;    

    
for  (i = 1 ; i <= adj[p][ 0 ]; i ++ {
        ts 
=  adj[p][i];
        
if  (ts  ==  pp)  continue ;
        dfs(ts, p);
        bk[ts][
0 =   0 ;
        bk[ts][
1 =   0 ;
        go[ts][
0 =   0 ;
        
for  (l = k; l >= 2 ; l -- ) bk[ts][l]  =  bk[ts][l - 2 +  w[ts];
        
for  (l = k; l >= 1 ; l -- ) go[ts][l]  =  go[ts][l - 1 +  w[ts];
        dp(p, ts);
    }

}


void  dp( int  x,  int  y)  {
    
int  i, j, l;
    
int  t1[N], t2[N];
    memset(t1, 
0 , sizeof(t1));
    memset(t2, 
0 , sizeof(t2));
    
for  (i = 0 ; i <= k; i ++ {
        
for  (j = 0 ; j <= i; j ++ {
            t1[i] 
=  max(t1[i], max(bk[x][j] + go[y][i - j], bk[y][j] + go[x][i - j]));
        }

    }

    
for  (i = 0 ; i <= k; i ++ {
        
for  (j = 0 ; j <= i; j ++ {
            t2[i] 
=  max(t2[i], bk[x][j] + bk[y][i - j]);
        }

    }

    
for (i = 0 ; i <= k; i ++ {
        bk[x][i] 
=  t2[i];
        go[x][i] 
=  t1[i];
    }

}

posted on 2007-02-10 18:55 阅读(1706) 评论(0)  编辑 收藏 引用 所属分类: ACM题目

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理