首页 > 代码库 > HDU 4340 树形DP
HDU 4340 树形DP
【题意】：
给你一张无向图，无向图上每个点代表一个城市，有两个值Va，Vb，分别代表a，b占领该城市所需要消耗的时间，而且a或b去占领它们已经占领的城市的相领城市所需的花费为标准的一般。问最少需要花费多少钱。
【知识点】：
树形DP
【题解】：
dp[u][i][0]：代表以u为根的子树中没有一个点为颜色i绘画开始点所需的最小花费，
即字数中画有i颜色的点的代价都为原来的一般
dp[u][i][1]：代表以u为根的子树中有一个点为颜色i绘画开始点所需的最小花费
u的子树中涂i色的点中有一个点为其本身的代价而不是其一半
【代码】：
1 #include <map> 2 #include <set> 3 #include <cmath> 4 #include <ctime> 5 #include <queue> 6 #include <stack> 7 #include <cstdio> 8 #include <string> 9 #include <vector>10 #include <cstring>11 #include <sstream>12 #include <iostream>13 #include <algorithm>14 #include <bitset>15 #include <climits>16 using namespace std;17 18 #define wh while19 #define inf (int)(~0u/2)20 #define FOR(i, n) for(int i = 0; i < n; i++)21 #define FOR1(i, n) for(int i = 1; i < n; i++)22 #define FOR2(i, n) for(int i = 0; i <= n; i++)23 #define REP(i,n) for(int i = 1; i <= n; i++)24 #define FORI(it,n) for(typeof(n.begin()) it = n.begin(); it != n.end(); it++)25 #define sf scanf26 #define pf printf27 #define frs first28 #define sec second29 #define psh push_back30 #define mkp make_pair31 #define PB(x) push_back(x)32 #define MP(x, y) make_pair(x, y)33 #define clr(abc,z) memset(abc,z,sizeof(abc))34 #define lt(v) v << 135 #define rt(v) v << 1 | 136 //#define mid ((l + r) >> 1)37 #define lson l, mid, v << 138 #define rson mid + 1, r, v << 1 | 139 40 #define fre freopen("1.txt", "r", stdin)41 42 typedef long long LL;43 typedef long double LD;44 const int INF = 0x3F3F3F3F;45 const int maxn = 120;46 vector<int> G[maxn];47 int dp[maxn][2][2];48 int cost[maxn][2]; int N;49 50 void dfs(int u, int fa){51 if(G[u].size() == 1 && fa != 0){52 FOR(i, 2){53 dp[u][i][0] = cost[u][i] / 2;54 dp[u][i][1] = cost[u][i];55 }56 return ;57 }58 FOR(i, (int)G[u].size()){59 int v = G[u][i];60 if(v == fa) continue;61 dfs(v, u);62 }63 FOR(i, 2){64 int sum = 0, cha = INF;65 int cst = cost[u][i];66 FOR(j, (int)G[u].size()){67 int v = G[u][j];68 if(v == fa) continue;69 int tmp = min(dp[v][i][0], dp[v][i ^ 1][1]); sum += tmp;70 cha = min(cha, dp[v][i][1] - tmp);71 //将原先选中的dp[v][i][0]或dp[v][i ^ 1][1]替换成dp[v][i][1]所需要的最小代价72 }73 dp[u][i][0] = cst / 2 + sum;74 dp[u][i][1] = min(cst + sum, cst / 2 + sum + cha);75 }76 }77 78 int main() {79 wh(sf("%d", &N) != EOF){80 REP(i, N) G[i].clear();81 REP(i, N) sf("%d", &cost[i][0]);82 REP(i, N) sf("%d", &cost[i][1]);83 REP(i, N - 1){84 int u, v; sf("%d%d", &u, &v);85 G[u].PB(v); G[v].PB(u);86 }87 dfs(1, 0);88 pf("%d\n", min(dp[1][0][1], dp[1][1][1]));89 }90 }
HDU 4340 树形DP
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。