ZOJ 3805 (树形DP)

题目链接: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5337

题目大意：方块连接，呈树形。每个方块有两种接法，一种接在父块边上，宽度+1,一种接在父块上面，宽度+0。且一个母块最多有2个子块。问全局的宽度最小是多少。

解题思路：

对于一个方块，就两种接法。

设dp[i][0]=0,表示接在父块上面。

dp[i][1]=1，表示接在父块边上。

对于一个父块，如果没有子块，宽度不变。

如果有一个子块，肯定接在上面，加上子块的宽度。

如果有两个子块，则有两种解法，max(左1上2),max(左2上1)，注意这里两个子块不是加起来，因为只要把管子伸长，让两个子块相互重叠掉一部分宽度，所以取max

那么接这两个子块就得加上这两种解法的较小值。（min）

最后结果是dp[1][1]，和dp[1][0]没关系，因为1块肯定要占一个宽度。

#include "cstdio"

#include "iostream"

#include "cstring"

using namespace std;

#define maxn 10005

struct Edge

{

    int next,to;

}e[maxn];

int dp[maxn][],head[maxn],tol;

void addedge(int u,int v)

{

    e[tol].to=v;

    e[tol].next=head[u];

    head[u]=tol++;

}

void dfs(int root)

{

    int cnt=,l1=,l2=,r1=,r2=;

    dp[root][]=,dp[root][]=;

    for(int a=head[root];a!=-;a=e[a].next) dfs(e[a].to);

    for(int a=head[root];a!=-;a=e[a].next)

    {

        int t=e[a].to;

        if(!cnt) {l1=dp[t][],l2=dp[t][];}

        else {r1=dp[t][],r2=dp[t][];}

        cnt++;

    }

    if(!cnt) return;

    else if(cnt==) {dp[root][]+=l1;dp[root][]+=l1;}

    else

    {

        int a=max(l1,r2),b=max(l2,r1);

        dp[root][]+=min(a,b);dp[root][]+=min(a,b);

    }

}

int main()

{

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

    int n,u;

    while(scanf("%d",&n)!=EOF)

    {

        memset(head,-,sizeof(head));

        tol=;

        for(int i=;i<=n;i++)

        {

            scanf("%d",&u);

            addedge(u,i);

        }

        dfs();

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

    }

}

3808409

2014-10-20 17:37:23

Accepted

3805

C++

800

468

Physcal

巴特西

ZOJ 3805 (树形DP)

最新文章

热门文章