poj2486 Apple Tree【区间dp】

转载请注明出处，谢谢：http://www.cnblogs.com/KirisameMarisa/p/4374766.html ---by 墨染之樱花

【题目描述】给一张顶点带权值的图，求从1号点出发走k步的最大总权值（顶点可以重复走）

【思路】经典的树形dp，本沙茶看了别人的题解才会orz。。。。详情请见下面的代码中的详细注释

/* ***********************************************

Author        :Kirisame_Marisa

blog          :http://www.cnblogs.com/KirisameMarisa/

Created Time  :2015年03月28日 星期六 18时56分45秒

File Name     :c.cpp

************************************************ */

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <ctime>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

using namespace std;

const int INF=0x3f3f3f3f;

const int MAXN=;

#define eps 1e-10

#define zero(x) (fabs(x)<eps)

#define REP(X,N) for(int X=0;X<N;X++)

#define REP2(X,L,R) for(int X=L;X<=R;X++)

#define CLR(A,X) memset(A,X,sizeof(A))

#define PB(X) push_back(X)

#define MP(X,Y) make_pair(X,Y)

#define IT iterator

#define test puts("OK")

typedef long long ll;

typedef pair<int,int> PII;

typedef vector<int> VI;

typedef vector<PII> VII;

int a[];

VI G[];

int V,k;

int dp[][][];    //dp[i][j][t]在i为根的子树中走k步,t=0表示不回到根,t=1表示回到根

void dfs(int u,int par)

{

    REP(i,G[u].size())

    {

        int v=G[u][i];

        if(v==par)

            continue;

        dfs(v,u);

        for(int j=k;j>=;j--)

        {

            //回到u只有一种情况:先后在v根子树中走p步,其他子树中走j-p-2步

            REP2(p,,j-)        //p表示在以v为根的子树中走p步,由于uv两点来回要两步,所以范围显然是0到j-2,下同

                if(dp[u][j-p-][]+dp[v][p][]>dp[u][j][])

                    dp[u][j][]=dp[u][j-p-][]+dp[v][p][];

            //不回到u有两种情况:1.u到v,在v子树中转一圈回到v,再回到u,最后走其他子树不再回来

            REP2(p,,j-)

                if(dp[u][j-p-][]+dp[v][p][]>dp[u][j][])

                    dp[u][j][]=dp[u][j-p-][]+dp[v][p][];

                              //2.走其他子树回到u,再到v,在v子树中不回来(会不会到v都行,因为只要不再回u,不过不考虑这个也能AC -_-b)

            REP2(p,,j-)        //由于uv之间只要走一次u到v,所以范围是0到j-1

                if(dp[u][j-p-][]+max(dp[v][p][],dp[v][p][])>dp[u][j][])

                    dp[u][j][]=dp[u][j-p-][]+max(dp[v][p][],dp[v][p][]);

        }

    }

}

int main()

{

    //freopen("in","r",stdin);

    //freopen("out","w",stdout);

    while(~scanf("%d%d",&V,&k))

    {

        REP(i,V)

            G[i].clear();

        REP(i,V)

            scanf("%d",&a[i]);

        REP(i,V)

            REP2(j,,k)

                dp[i][j][]=dp[i][j][]=a[i];   //初始化

        REP(i,V-)

        {

            int x,y;

            scanf("%d%d",&x,&y);

            x--;y--;

            G[x].PB(y);

            G[y].PB(x);

        }

        dfs(,-);

        printf("%d\n",max(dp[][k][],dp[][k][]));

    }

    return ;

}

代码君

秒客网

poj2486 Apple Tree【区间dp】

相关文章