FZU 2157 树形DP

最开始一直不理解题是什么意思 ╯▽╰

题意：给出n个点，每个点都有两种花费，一个是0种花费，一个是1种花费，每两个点相连，边也有花费，是随着点所取话费的种类不同，边的花费也不同，边有四种花费，00，01，10，11 问建成整颗树所需要的最少花费。

思路：dp[i][0]代表当前结点取0种花费时建好以i结点为根节点的最少花费，dp[i][1]代表当前结点取1种花费时建好以i结点为根节点的最少花费，那么有动态转移方程就出来了.......

Sample Input

3 1 1 3

4 0 0 4

1 2 0 1 1 0

2 3 0 1 1 0

2 4 0 1 1 0

Sample Output

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

struct node

{

    int y;

    int a,b,c,d;

};

vector<node>q[200005];

int dp[200005][2];

int num1[200005];

int num2[200005];

void dfs(int u)

{

    if(q[u].empty())

    {

        dp[u][0] = num1[u];

        dp[u][1] = num2[u];

        return;

    }

    dp[u][0] = num1[u];

    dp[u][1] = num2[u];

    int len = q[u].size();

    for(int i = 0; i < len; i++)

    {

        node tmp = q[u][i];

        dfs(tmp.y);

        dp[u][0] += min(dp[tmp.y][0]+tmp.a,dp[tmp.y][1]+tmp.b);

        dp[u][1] += min(dp[tmp.y][0]+tmp.c,dp[tmp.y][1]+tmp.d);

    }

}

int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

        int n;

        scanf("%d",&n);

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

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

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

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

        memset(dp,0,sizeof(dp));

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

            q[i].clear();

        int x,y,a,b,c,d;

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

        {

            scanf("%d%d%d%d%d%d",&x,&y,&a,&b,&c,&d);

            node temp;

            temp.y = y;

            temp.a = a;

            temp.b = b;

            temp.c = c;

            temp.d = d;

            q[x].push_back(temp);

        }

        dfs(1);

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

    }

    return 0;

}

巴特西

FZU 2157 树形DP

Sample Input

Sample Output

最新文章

热门文章