POJ 2486 Apple Tree

题目意思:一个N 个节点的苹果树,每个节点有一定数目的苹果;问从1 出发走K步 所能迟到的苹果(每一步只可以到相邻的节点)

  解法:

  走法包含以下基本的情况(其他的走法都可以由以下的组合出来):

  1:在树上头也不回的往前;

  2:回到走过的节点再去别的节点:

  所以对于每个节点有一个 flag 走了没回来?还是走过又回来了 !

其他的就是背包的只是了依赖性的01背包么!

  dp[flag][i][j]// 节点I的子树内走J步 flag=1 代表没回到I,flag=0 代表回到了I

  dp[0][s][i+2]=max(dp[0][s][i+2],dp[0][s][j]+dp[0][tmp.to][i-j]);// 经由新的子树在回来所以要+2
  dp[1][s][i+2]=max(dp[1][s][i+2],dp[1][s][j]+dp[0][tmp.to][i-j]);// 经由新的子树再回来,且进入原来的树,所以要加2
  dp[1][s][i+1]=max(dp[1][s][i+1],dp[0][s][j]+dp[1][tmp.to][i-j]);// 经由原来的树,进入新的数,+1
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
using namespace std;
const int maxn=105;
const int INF=0x3fffffff;
struct Edge
{
    int to,dis,pre;
    Edge(int to=0,int dis=0,int pre=0):to(to),dis(dis),pre(pre){}
};
Edge edge[maxn];
int head[maxn],pos;
int dp[2][maxn][205];
int num[maxn];
int N,K;
void inint()
{
    memset(head,-1,sizeof(head));
    pos=0;
}
void add_edge(int s,int to,int dis)
{
    edge[pos]=Edge(to,dis,head[s]);
    head[s]=pos++;
}
void dfs(int pa,int s)
{

    for(int i=0;i<=K;i++)
        dp[0][s][i]=dp[1][s][i]=num[s];
    for(int w=head[s];~w;w=edge[w].pre)
    {

        Edge &tmp=edge[w];
        if(tmp.to==pa)continue;
        dfs(s,tmp.to);
        for(int i=K;i>=0;i--)
        {
            for(int j=0;j<=i;j++)
            {
                dp[0][s][i+2]=max(dp[0][s][i+2],dp[0][s][j]+dp[0][tmp.to][i-j]);
                dp[1][s][i+2]=max(dp[1][s][i+2],dp[1][s][j]+dp[0][tmp.to][i-j]);
                dp[1][s][i+1]=max(dp[1][s][i+1],dp[0][s][j]+dp[1][tmp.to][i-j]);
            }
        }
    }
}
int main()
{
    int a,b;
    while(~scanf("%d%d",&N,&K))
    {
        inint();
        for(int i=1;i<=N;i++)scanf("%d",&num[i]);
        for(int i=2;i<=N;i++)
        {
            scanf("%d%d",&a,&b);
            add_edge(a,b,1);
            add_edge(b,a,1);
        }
        dfs(-1,1);
        printf("%d\n",dp[1][1][K]);
    }
    return 0;
}

 

 

POJ 2486 Apple Tree,布布扣,bubuko.com

POJ 2486 Apple Tree

上一篇:iOS推送的开启与关闭


下一篇:iOS的开发者的webview的js性能比Safari性能差5、6倍