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就是单着的那个数. ...
一周排行
  • #include <iostream> using namespace std; int qh_num(int a)//该函数主要用来获得数a的亲和数 { int sum = 0; for(int i = ...
  • 在生活中,我们总会遇到各种各样的问题,这个时候,我们通常向身边的朋友或者专业人士请教,以获得经验交流或问题的解决辦法.在网络上,人们则通过百度知道.知乎这样的问答渠道获取别人的幫助. 百度知道.知乎这样的平台,我们通
  • yum groupinstall Virtualization "Virtualization Client" yum install libvirt libguestfs-tools 1.下载一 ...
  • LDPI (Low Density Screen,120 DPI),其图标大小为 36 x 36 px.MDPI (Medium Density Screen, 160 DPI),其图标大小为 48 x 48 px. ...
  • 本人用Loader加载外部一个swf.之后unloadAndStop,Flash概要分析发现,内存没有被释放. 网上搜了一大堆文章,要么就是加载bitmapdata之后,自己dispose,要么就是加载自己的接口id
  • 编辑文件Xcacls.vbs,查找Case "5.0", "5.1", "5.2"更改为Case "5.0", "5.1&qu ...
  • WPF學習(11)2D繪圖
    本篇我们来学习WPF的绘图,在2D绘图中主要有这么几个重要的类:Drawing.Visua
  • 近日,工作的事情较少,闲来无事:同事忽然提起获取IP那点事,于是整理一点关于Get IP的一些方法记于此!!! 一.首先来一个正则表达式(结合grep) 点分十进制IP: egrep -o "\<([ ...
  • P253 P257~P268 P310~P312 P316~P320 P335 P336-表3.2. P340 P341 P342 至表7.0.为止,B系列不输入 P352~P353 P360 P363~ ...
  • AX2012 R3關于Named user license report
    Named user license报表是用来统计各种授权类型用户数的,这里来看看报表数据 ...