专栏首页饶文津的专栏【HDU - 4340】Capturing a country(树形DP)

【HDU - 4340】Capturing a country(树形DP)

BUPT2017 wintertraining(15) #8A

题意

n(<100)个城市组成的树。A攻击i城市需要a[i]代价,B需要b[i]。如果一个城市的邻居被A攻击了,那么A攻击它只要A[i]/2(整除)的代价,B同理。求攻击全部城市的最小代价。

题解

这题很容易想到树形dp。 每个节点为根的子树,有可能是: A从根的上面攻击下来, A从根或下面攻击到根上面, B从根的上面攻击下来, B从根或下面攻击到根上面。 于是设计状态 dp[i][0..1][0..1]分别对应i为根的子树上面四种状态下攻击整个子树的最小代价。

然后dfs,在回溯的时候进行状态转移。

代码

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define N 105
#define inf 0x3f3f3f3f
struct edge{
	int to,next;
}e[N<<1];
int head[N],cnt;
void add(int u,int v){
	e[++cnt]=(edge){v, head[u]};
	head[u]=cnt;
}
int a[N],b[N];
int dp[N][2][2];
int f[N][2];
void dfs(int x, int fa){
	//ha:先用A攻击x,再攻击它子树的最少花费
	int ha=0,hb=0;
	for(int i=head[x];i;i=e[i].next){
		int v=e[i].to;
		if(v==fa)continue;
		dfs(v,x);
		//如果A攻击了x,儿子i为根的子树的最小花费就是min(A下去攻击i,或者B攻上来到i)。
		ha+=min(dp[v][0][0],dp[v][1][1]);
		hb+=min(dp[v][1][0],dp[v][0][1]);
		f[x][0]=min(f[x][0],f[v][0]);//f[i][0]:min(A先攻击i的某个子节点-不用A先攻击该子节点),就是最小的增加量。
		f[x][1]=min(f[x][1],f[v][1]);
	}
	dp[x][0][0]=ha+a[x]/2;
	dp[x][1][0]=hb+b[x]/2;

	//x的儿子里选一个先攻击,就要加上f[x][0]+a[x]/2(半价攻击x)
	//先攻击x,就要加上a[x](全价攻击x)
	dp[x][0][1]=ha+min(f[x][0]+a[x]/2, a[x]);
	dp[x][1][1]=hb+min(f[x][1]+b[x]/2, b[x]);
	//如果选择不用A从下往上攻击x节点,我们肯定要选其它方案里花费最小的一种。所以取min。
	f[x][0]=dp[x][0][1]-min(dp[x][0][0], dp[x][1][1]);
	f[x][1]=dp[x][1][1]-min(dp[x][1][0], dp[x][0][1]);
}
int n;
void init(){
	cnt=0;
	memset(head, 0,sizeof head);
	memset(dp, 0, sizeof dp);
	memset(f, inf, sizeof f);
}
void work(){
	for(int i=1;i<=n;++i)
		scanf("%d",a+i);
	for(int i=1;i<=n;++i)
		scanf("%d",b+i);
	for(int i=1,x,y;i<n;++i)
		scanf("%d%d",&x,&y),add(x,y),add(y,x);
	dfs(1,0);
		printf("%d\n",min(dp[1][1][1], dp[1][0][1]));
	}
int main(){
	while(~scanf("%d", &n)){
		init();
		work();
	}
}

ps.这题四个月前补过一次,今天又不会了。花了好久才明白。主要是状态的设计和转移。我觉得我这种转移写法也许算是比较难理解和直接写出来的,我当时是参考了别的题解再改了改。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【USACO 2.3】Money Systems(dp)

    dp[i][j]表示前i种货币价格为j有多少种方案,dp[i][j]+=dp[i-1][j-c]。

    饶文津
  • 【CodeForces 577B】Modulo Sum

    给你n(1 ≤ n ≤ 106)个数a1..an(0 ≤ ai ≤ 109),再给你m( 2 ≤ m ≤ 103)如果n个数的子集的和可以被m整除,则输出YES...

    饶文津
  • 【HDU - 4341】Gold miner(分组背包)

    给出每个黄金的坐标、价值及耗时,同一方向的黄金只能依次取,求T时间内收获的最大值。

    饶文津
  • P1004 方格取数

    题目描述 设有N*N的方格图(N<=9),我们将其中的某些方格中填入正整数,而其他的方格中则放 人数字0。如下图所示(见样例): A 0 0 0 0 ...

    attack
  • POJ 2192 Zipper HDU 2059 龟兔赛跑

    owent
  • 最长公共连续子串

    牛牛有两个字符串(可能包含空格),牛牛想找出其中最长的公共连续子串,希望你能帮助他,并输出其长度。 输入描述: 输入为两行字符串(可能包含空格),长度...

    AI那点小事
  • 张高兴的 .NET Core IoT 入门指南:(四)使用 SPI 进行通信

    和上一篇文章的 I2C 总线一样,SPI(Serial Peripheral Interface,串行外设接口)也是设备与设备间通信方式的一种。SPI 是一种全...

    张高兴
  • 月球上的水不是普通水,可喝可用作火箭燃料 | 黑科技

    镁客网
  • iOS开发一款小巧简洁的日历控件 原

            日 历是iOS开发中有时会用到的一个UI控件,网上开源的代码也很多,我浏览过一些,大致有两种模式,一种是日历的逻辑由开发者自己实现,通过计算闰年...

    珲少
  • 印度失联的月球探测器依然成功了95%?那些年我们一起追过的月球

    古往今来,人们对月球一直充满了好奇与幻想,古有“举杯邀明月,对影成三人”、“今人不见古时月,今月曾经照古人”,今有“我望见有两个月亮:一般的样,不同的相”、“我...

    大数据文摘

扫码关注云+社区

领取腾讯云代金券