zoj 3201

83 阅读 0 评论 55 点赞

我是靠谱客的博主忧伤冬日，最近开发中收集的这篇文章主要介绍zoj 3201，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

和前面的那个题思路差不多一个很简单的树状dp 之前没有过在初始化的时候有一点问题 wa了两次

状态转移方程：dp[u][j+k] = max ( dp[u][j+k] , dp[u][j] + dp[v][k] );

然后注意到dp[u][j]可能被前面所覆盖，所以需要初始化一下

来保存一下然后就ac

#include <iostream>

    #include <stdio.h>
    #include <vector>
    #include <cstring>
    using namespace std;

    const int MAXN = 250;
    int dp[MAXN][MAXN];
    int w[MAXN];
    int vis[MAXN];
    vector < int > adj[MAXN];
    int n,k;

    void dfs ( int u )
    {
        //cout << u << endl;
        dp[u][1] = w[u];
        dp[u][0] = 0;
        vis[u] = 1;
        for ( int i = 0 ; i < adj[u].size(); i ++ )
        {
            int v = adj[u][i];
            //cout << "***" << v << endl;
            if ( vis[v] )    continue;
            dfs ( v );

            int temp[MAXN];
            for ( int j = 0 ; j <= n ; j ++ )
                temp[j] = dp[u][j];
            for ( int j = 1 ; j <= n ; j++ )
                for ( int k = 0 ; k+j <= n ; k ++ )
                {
                    dp[u][j+k] = max ( dp[u][j+k] , temp[j] + dp[v][k] );
                }
        }
    }
    int main()
    {
        while ( cin >> n >> k )
        {
            for ( int i = 0 ;i < MAXN ; i ++ )
                adj[i].clear();
            memset ( vis , 0 , sizeof ( vis ));
            memset ( dp , 0 , sizeof ( dp ));
            for ( int i = 0 ; i < n ;i ++ )
                cin >> w[i];
            for ( int i = 0 ; i < n-1 ;i ++ )
            {
                int a, b;
                cin >> a >> b;
                adj[a].push_back( b );
                adj[b].push_back( a );
            }
            //cout << "here" << endl;
            dfs ( 0 );
    //        for ( int i = 0 ; i < n ; i ++ )
    //            for ( int j = 0 ; j < adj[i].size(); j ++ )
    //                printf("%d ===== %d ==== %d n" , i , j , adj[i][j] );
//            for ( int i = 0 ; i < n ;i ++ )
//                for ( int j = 0 ; j <= n ; j ++ )
//                    printf("dp[%d][%d] = %dn" , i , j , dp[i][j] );
            int ans = 0 ;
            for ( int i = 0 ; i < n ; i ++ )
                ans = max ( ans , dp[i][k] );
            cout << ans << endl;

        }

        return 0;
    }