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

发布时间:2017-7-9 7:13:28编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"【HDU - 4340】Capturing a country(树形DP) ",主要涉及到【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 0x3f3f3f3fstruct 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.这题四个月前补过一次,今天又不会了。花了好久才明白。主要是状态的设计和转移。我觉得我这种转移写法也许算是比较难理解和直接写出来的,我当时是参考了别的题解再改了改。


上一篇:Storyboard的几点缺憾
下一篇:Flask刷新问题

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款