uva 12452 Plants vs. Zombies HD SP (樹DP)

Problem I: Plants vs. Zombies HD Super Pro

Plants versus Zombies HD Super Pro is a game played not a grid, but on a connected graph G with no cycles (i.e., a tree). Zombies live on edges of the tree and chew through edges so that tree falls apart! Plants can be purchased and placed on vertices of the tree to protect the tree from falling apart. It is not possible to plant more than one plant on the same vertex. A plant protects one or more adjacent edges, depending on the strength and capabilities of the plant.

 

The Almanac offers you to buy any of three different types of plants:

  • PEASHOOTERS: These are your first line of defense and can shoot peas along any one edge (of your choosing) adjacent to the vertex upon which it is placed. Cost: $100 per plant.
  • SPLIT PEAS: These are hard working pea shooters and can shoot peas along any two edges (of your choosing) adjacent to the vertex upon which it is placed. Cost: $175 per plant.
  • STARFRUIT: Having just visited the dentist, a STARFRUIT is very upset and shoots stars along all edges adjacent to the vertex upon which it is placed. Cost: $500 per plant.

Your goal is to protect the tree from the Zombies by having every edge covered by at least one plant, and doing so spending the least amount of money. You can buy more than one of each type of plant, but you can only plant at most one plant on each vertex.

 

Input Format

The input starts with an integer T - the number of test cases (T <= 100). T cases follow, each starting with the integer N on the first line, the number of vertices in G (2 <= N <= 10,). N-1 line follows, each containing two space separated integers u and v (0 <= u,v <= N-1, u ≠ v) - describing an edge.

Output Format

For each test case, print on a separate line the minimum cost of protecting the tree, formatted like in the sample output.

Sample Input

2
2
0 1
3
0 1
1 2

Sample Output

$100
$175

In the second case we can put a Split Pea on the vertex 1.

 


题意: 给一颗n个点的树,每个点上只能放一种植物,共有三种植物,第一种可以覆盖与种植点相邻的一条边,费用是100,第二种是可以覆盖两条边,费用是175,第三种是可以覆盖所有边,费用500。求最小花费的金额,使得树上每一条边都能被覆盖。

 

思路:果断树DP。设dp[u][0]表示以u为根节点且u不覆盖u到他父亲节点的边的最小费用,dp[u][1]表示以u为根节点且u覆盖u到他父亲节点的边的最小费用。

然后分四种情况考虑状态转移。以下用v表示u的子节点

1.u不种植物:dp[u][0] = dp[v][1],而且不种植物是不可能连接父节点,即无dp[u][1]

2.u种第一种: dp[u][0] = dp[v][0] (选一个子节点) + dp[v][1] (剩余的所有子节点之和) + cost[1]

                  dp[u][1] = dp[v][1] (所有子节点之和) + cost[1]

3.u种第二种: dp[u][0] = dp[v][0](选两个子节点) + dp[v][1] (剩余所有子节点) + cost[2]

                  dp[u][1] = dp[v][0] (选一个子节点) + dp[v][1] (剩余所有子节点) + cost[2]

4.u种第三种: dp[u][0] 是不可能的

                 dp[u][1] = dp[v][0/1](所有子节点) + cost[3]

至于选择哪一个子节点,这里要用贪心,选一个差值最大的来搞,记录下sum1和sum0,以及最大差值dmx,次大差值dmx2

注意下使用第三种植物的时候不能简单用sum1和sum0,因为有dp[v][1] < dp[u][0]的情况存在,今天比赛就是坑这个位置了,遗憾啊。。

 

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int INF = 1e9;
const int N = 10010;

struct _edge{
int v,next;
};
_edge edge[N*2];
int first[N],n,ecnt;
int dp[N][2];
int cost[5];

inline void add(int u,int v)
{
edge[ecnt].v = v;
edge[ecnt].next = first[u];
first[u] = ecnt++;
}

void dfs(int u,int fa)
{
dp[u][0] = dp[u][1] = INF;
bool flag = 1;
int sum1,sum0,dmx,dmx2;
sum1=sum0=0;
int sum3=0;
dmx=dmx2=0;
for(int e=first[u];e!=-1;e=edge[e].next)
{
int v = edge[e].v;
if(v==fa) continue;
flag = 0;
// 1:
dfs(v,u);
sum1 += dp[v][1];
sum0 += dp[v][0];
sum3 += min(dp[v][1],dp[v][0]);
int d = dp[v][1]-dp[v][0];
if(d>dmx2)
{
dmx2 = d;
if(dmx2 > dmx)
{
swap(dmx,dmx2);
}
}
}
if(flag)
{
dp[u][0]=0;
dp[u][1]=cost[1];
return;
}
dp[u][0] = min(sum1 - dmx + cost[1],sum1 - dmx - dmx2 + cost[2]);
dp[u][0] = min(dp[u][0],sum1);
dp[u][1] = min(min(sum1 + cost[1],sum1 - dmx + cost[2]),sum3 + cost[3]);
}

void run()
{
memset(first,-1,sizeof(first));
ecnt=0;
scanf("%d",&n);
int u,v;
for(int i=1;i<n;i++)
{
scanf("%d%d",&u,&v);
add(u,v);
add(v,u);
}
dfs(0,-1);
// for(int i=0;i<n;i++)
// {
//// printf("%d: %d %d\n",i,dp[i][0],dp[i][1]);
// }
printf("$%d\n",min(dp[0][0],dp[0][1]));
}

int main()
{
//freopen("in","r",stdin);
cost[1]=100;cost[2]=175;cost[3]=500;
int _;
scanf("%d",&_);
while(_--)
run();
return 0;
}

 

更多相关文章
  • 


    		    本月最佳游戏《植物大战僵尸(Plants vs. Zombies)》29MEN
    中文名称:植物大战僵尸 英文名称:Plants vs. Zombies 发行时间:2009年05月05日 游戏类型:益智 游戏语言:英文 开发厂商:PopCap Games 发行厂商:PopCap Games 游戏介绍: 一个看似简单实则极富策略性的小游戏,游戏中你需要建造各种植物来阻挡僵尸进入庄园 ...
  • 题意:求树上的一条费用不超过m的路径,使得总长度尽量大. 人参第一发树分治,紫书上思路讲得比较清晰,这里不再赘述. 实现的时候,用一个类似时间戟的东西,记录结点首次访问的时间,并保存结点序列. 合并的时候用map组织
  • 题目给出一个后缀表达式,让你求从下往上的层次遍历. 思路:结构体建树,然后用数组进行BFS进行层次遍历,最后把数组倒着输出就行了. uva过了,poj老是超时,郁闷. 代码: #include <cstdio> #include <cstring> #include < ...
  • 题目要求可转化为查询一个区间内有多少数比val大(或者小). 区间用线段树分解(logN),每个区间维护一rank树. rank可用BIT查询,往BIT里面插值,为了保证不同区间的BIT互不影响要先离散. 首先进行分治,分治的同时归并排序完成离散并计算保存出每个元素和其他元素构成的逆序对iv[i]. ...
  • UVa 12299 RMQ with Shifts(線段樹)
    线段树,没了..--#include<cstdio>#include<cstring>#i
  • 题目描述: 一个由n个部门组成的公司现在需要分层,但是由于员工间的一些小小矛盾,使得他们并不愿意做上下级,问在满足他们要求以后有多少种分层的方案数? 解题思路: 生成树计数模板题,建立Kirchhoff矩阵,利用Matrix_tree定理求解. Kirchhoff矩阵:假设G为n*n矩阵,C为G的入
  • UVA 1416	 Warfare And Logistics 最短路樹
    对每个点求最短路,同时求出最短路树. 枚举每条边,如果这条边在最短路树上,那么删掉这条边就需要重新计算最短路,否则不需要. //#pragma comment(linker, "/STACK:1024,1024") #include<cstdio> #include& ...
  • 原题链接:http://acm.bnu.edu.cn/bnuoj/problem_show.php?pid=4060 分析:         解法一:注意到这里只有一个数据的单起来的,其他都两两配对,有进有出(被杀死).那么我们用sum表示他们的和,进则加,出则减.最好剩下的sum就是单着的那个数. ...
一周排行