Sicily 1019 Apple Tree (SOJ 1019)「树形dp 树形动态规划」

0.00 avg. rating (0% score) - 0 votes
转载请注明: 吹水小镇 | reetsee.com
原文链接地址: http://blog.reetsee.com/archives/32

原题地址:点击打开链接

这题也是蓄谋已久,很久之前就看过,但是十分没有头绪,在搜了一下答案后发现要用树形dp,当时问了周生什么是树形dp,周生直说是他非常不想碰的一种东西。好吧当时我一听吓尿了干脆也不碰了。

但是下定决心解决它的日子也到了···毕竟省赛不能拖子畦大牛的后腿,也在经过几次面试后知道算法的莫大重要性(尽管暂时的水平应对面试还凑合,但是无法给面试官一种“quite smart”的感觉)。

其实我也想多做题,但是做题总有这么一种困境出现:我限定每道题单次思考时间最多30分钟,完全没头绪就上网搜下答案,问题是在这30分钟内你会出现那么一些clues,你感觉很接近问题的答案,于是就思忖怎么实现代码,流程如何,接着想着怎么去改进。问题在于有时候我可以同时有几个Backup Plans,我会想如果这些方案全部都不行,那么就查答案,于是就处于不断“试错”的阶段,等黔驴技穷,过去的时间何止30分钟,有时候可能几个小时就没了,这个时候觉得何等痛苦,就是撞了一头包,但还是没有解决问题。

不过这么多次碰壁也是有点收获的,一旦看到题目,先不要记住将思路实现,考虑大体框架,觉得没什么问题再深入,这样可以避免频繁地增删改查;另外一个是在上网查答案的时候,可以先不要急着看代码,通常每道题目会有提示,例如DP,树形DP,深搜,广搜之类的,往哪个方向先想下,实在不行再使用“查看代码”这个 Big Hammer(广东话俗称大绝)。如果获得的提示是不太了解的,可以先去看一下相关资料(鄙人目前将《算法导论》作为handbook使用····)

不好意思,废了那么多口舌还没有进入正文····来了来了

——————正文————————

首先,我对别人的代码有所参考,但是搜出来的代码讲解都不那么详细,所以我这里也把自己的想法重新组织一下,希望可以帮到那些被这题困住的同学

参考网址:http://a234126477.blog.163.com/blog/static/173132150201141505656595/  (感谢GOOGLE搜到这个)

    http://denglele.diandian.com/post/2013-02-08/40048689255(感谢SOSO搜到这个)

在自己做前,我主要参考这两个地方的代码,当然最烦恼的是,我竟然看不懂代码!而且是死盯没看出来所以然,后来问了周生才解决。

我的代码与参考网址中的有不同

这里,对于没了解过树形DP的同学,可以看一下这个PPT,有值得参考的地方:http://download.csdn.net/detail/fanfank/5325841

条目本身,要注意的地方有:是一棵树     可以走回头路     走过重复节点不会累加苹果

对于每个节点及其子节点,有以下两种关系:

一种是在走完子节点后,会回到父节点,如下左图;另外一种是在走到子节点后,不会再返回到父节点,如下右图

走完子节点不回父节点 走完子节点回父节点

假设到了B节点后还有KK步没有走,那么可以怎么分配?假如我分配给左子树J步(那么C节点实际可用只有J-2步),那么在情况1,走完C节点后回到B节点会剩余KK-J步;而在情况2,子节点C肯定不会返回,但是对其所属子树分配J步(而J不一定等于KK-1)也是有意义的,因为使用树形DP的时候要对子树的情况进行合并,除了当前计算的子树外,其实还有其它子树的情况没有合并,因此即便是情况2,在写代码时也不能直接将所有剩余步数分配给子树,这是我觉得最难的地方,看别人的代码很难看出所以然(PS:也可能因为我悟性低)。

现在我们讨论转移方程,虽然我感觉由自己说这个转移方程是怎么来的有点扯(因为根本不是我想出来的),但我还是说一下好了····根据节点编号、剩余步数、是否返回到父节点这三个变量,我们很神奇地(!=_=)可以定义dp[x][y][z]的意思为:编号为x的节点剩余y步时在返回(z=0)或者不返回(z=1)时能够拿到的最多苹果数。

然后根据上面的两种情况,假设当前计算的某个节点(设为cur),其剩余步数是kk,其分配给当前计算的子树(son为第一个节点)的步数为j,那么转移方程为:

if(j>=2)  //j>=2则有可能子树返回
{
	max0=max(max0, dp[cur][kk-j][0]+dp[son][j-2][0]);
	max1=max(max1, dp[cur][kk-j][1]+dp[son][j-2][0]);
}
if(j>=1) //j>=1则有可能子树不返回,如果子树不返回,则当前节点也不会返回
  max1=max(max1, dp[cur][kk-j][0]+dp[son][j-1][1]); //这里为什么不是dp[cur][kk-j][1] ?

最后有

dp[cur][kk][0]=max(max0, dp[cur][kk][0];
dp[cur][kk][1]=max(max1, dp[cur][kk][1];

关于上面再上面的代码,为什么是“dp[cur][kk-j][0]+dp[son][j-1][1]” ?为什么不是“dp[cur][kk-j][1]+dp[son][j-1][1]”?(各位可以先看一下下面的代码,好对代码整体有所了解再回来看。)

因为dp[cur][…][0]保存的内容实质是之前的其它子树合并后的结果,而这里在考虑当前的子树不返回的情况下,就证明其它的所有子树必须是返回的,因为不存在两棵同时不返回的子树,所以这里要用dp[cur][…][0]+dp…来更新max1。这里是比较难说明的,还是要花点功夫理解。

最后就是代码了:

#include<iostream>
#include<memory.h>
#include<stdio.h>
#include<vector>
#include<cmath>
#include<algorithm>
#define MAXN 250
using namespace std;
int n,k,tmpa,tmpb;
int a[MAXN];
int dp[MAXN][MAXN][2];
vector<int> v[MAXN];
bool isv[MAXN];
void compute(int cur, int depth)
{
	isv[cur]=true;
	if(depth>k)
	  return;
	for(int i=0;i<v[cur].size();++i)
	{
	  int son = v[cur][i];
	  if(!isv[son])
	  {
		compute(son, depth-1);
		for(int kk=k-depth; kk>=0; --kk)
		{
		  int max0=a[cur];
		  int max1=a[cur];
		  for(int j=kk;j>=1;--j) //此处j表示cur剩余可用的步数,和之前给出的参考内容不同
		  {
			if(j>=2)  //j>=2则有可能子树返回
			{
			  max0=max(max0, dp[cur][kk-j][0]+dp[son][j-2][0]);
			  max1=max(max1, dp[cur][kk-j][1]+dp[son][j-2][0]);
			}
			if(j>=1) //j>=1则有可能子树不返回,如果子树不返回,则当前节点也不会返回
			  max1=max(max1, dp[cur][kk-j][0]+dp[son][j-1][1]); //这里不是dp[cur][kk-j][1],因为其它子树必须是返回的,所以需利用全部返回的dp 
		  }
		  dp[cur][kk][0]=max(max0,dp[cur][kk][0]);
		  dp[cur][kk][1]=max(max1,dp[cur][kk][1]);
		}
	  }
	}
}
int main()
{
  //freopen("in.in","r",stdin);
  //freopen("out.out","w",stdout);
  while(scanf("%d%d",&n,&k)!=EOF)
  {
	memset(dp,0,sizeof(dp));
	memset(isv,0,sizeof(isv));
	for(int i=1;i<=n;++i)
	  v[i].clear();
	for(int i=1;i<=n;++i)
	  scanf("%d",&a[i]);
	for(int i=1;i<n;++i)
	{
		scanf("%d%d",&tmpa,&tmpb);
		v[tmpa].push_back(tmpb);
		v[tmpb].push_back(tmpa);
	}
	for(int i=1;i<=n;++i)
	  for(int j=0;j<=k;++j)
		dp[i][j][0]=dp[i][j][1]=a[i];
	compute(1,0);
	cout<<max(dp[1][k][0],dp[1][k][1])<<endl;
  }
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注