现在的位置: 首页 > 综合 > 正文

ZOJ 2834 Maximize Game Time

2018年03月18日 ⁄ 综合 ⁄ 共 2667字 ⁄ 字号 评论关闭

 07年浙大赛的一题。TreeDp。感谢某位不知名牛人。

 

/*
每次遍历子结点来进行DP过程。
每个结点保留下3个值,
以它为跟的树所有结点值的和(结点数)totel,
进行到这个结点的最优值finish,
以及不能走到当前结点,子结点最多可以走的数目。
这样,每个结点的3个值都可以通过所有子结点的值来确定。
计算完毕后,需要注意的是这题里的数据可能是一个森林,不在要求树中的所有结点可以全部加上去。
*/


#include 
<cstdio>
#include 
<string>
#include 
<cstdlib>

#define minLen 1
#define nMax 1001
#define rg(x,y) ( x = x > y ? x : y )

int N;
int root,
total;
int par[nMax],
val[nMax],
sum[nMax],        
// 结点为根的树的sum
c[nMax],        // 刚好完成此根时的point
uc[nMax];        // 未完成此根时的最大point

class Son
{
public:
    
int *p;
    
int len;    // 当前子结点数目
    int lMax;    // 数组大小
    Son ()
    
{
        p 
= new int[minLen];
        len 
= 0, lMax = minLen;
    }

    
void Set ()
    
{
        len 
= 0;
    }

    
void Insert ( int x )
    
{
        
if ( len == lMax )
        
{
            
int *t;
            t 
= new int[len << 1];
            memcpy ( t, p, 
sizeof ( int ) * len );
            p 
= t;
            t 
= NULL;
            lMax 
<<= 1;
        }

        p[len 
++= x;
    }

}
;
Son l[
1000];    // 所有节点

int init ()
{
    scanf ( 
"%d"&N );
    
if ( N == 0 )
        
return 0;
    
int i;
    total 
= 0;
    
for ( i = 0; i < N; i ++ )
    
{
        scanf ( 
"%d"&val[i] );
        total 
+= val[i];
        l[i].Set ();
    }

    
for ( i = 0; i < N; i ++ )
    
{
        scanf ( 
"%d"&par[i] );
        
if ( par[i] == -1 )
            root 
= i;
        
else
            l[par[i]].Insert ( i );        
    }

    
return N;
}


void search ( int u )
{
    
int i;
    sum[u] 
= val[u];
    c[u] 
= val[u];
    uc[u] 
= 0;
    
if ( l[u].len == 0 )
        
return;
    
if ( l[u].len == 1 )
    
{
        sum[u] 
+= val[l[u].p[0]];
        c[u] 
+= val[l[u].p[0]];
        uc[u] 
+= val[l[u].p[0]];
        
return;
    }

    
for ( i = 0; i <l[u].len; i ++ )
    
{
        search ( l[u].p[i] );
    }

    
int tSum = 0;
    
for ( i = 0; i < l[u].len; i ++ )
    
{
        sum[u] 
+= sum[l[u].p[i]];
        tSum 
+= uc[l[u].p[i]];
    }

    
int j;
    
// 枚举2
    int max = 0;
    
int pi, pj;
    
for ( i = 0; i < l[u].len; i ++ )
    
{
        pi 
= l[u].p[i];
        
for ( j = 0; j < l[u].len; j ++ )
        
{
            
if ( i == j )
                
continue;
            pj 
= l[u].p[j];
            
// 第一个用sum[pi]填满,第二个子结点放入后则立刻转移至u
            rg ( max, tSum - uc[pi] + sum[pi] - uc[pj] + c[pj] );
        }

    }

    c[u] 
+= max;
    max 
= 0;
    
for ( i = 0; i < l[u].len; i ++ )
    
{
        pi 
= l[u].p[i];
        
// 只能填满一个子结点
        rg ( max, tSum - uc[pi] + sum[pi] );
    }

    uc[u] 
+= max;
}


int main ()
{
    
//freopen ( "in.txt", "r", stdin );
    
//freopen ( "out.txt", "w", stdout );
    while ( init () )
    
{
        search ( root );
        
// 数据可能是森林
        printf ( "%d ", total - sum[root] + c[root] );
        
//pt ();
    }

    
return 0;
}

抱歉!评论已关闭.