解题报告

NOI2002上第一试的第三题

贪吃九头龙

题目描述：

暂略

题目分析：

首先我们考虑对其它小头的处理，我们发现对于m>3，当大头把该吃的吃完后，其他的头可以毫不费难受度将果子吃完，对于一个树枝，可以一个小头吃一端的果子，另一小头吃另一端的果子。

于是问题转换为将以i为根的树大头吃k个的最小难受度，由于是多叉树，我们首先考虑将它转换为更好处理的二叉树，于是我们又以下方程：

f[i,j,k]=min{ f[x1,j1,1]+f[x2,j-j1-1,k]+d[k,1]*cost[i,father[i]]——i给小的吃

f[x1,j1,0]+f[x2,j-j1,k]+d[k,0]*cost[i,father[i]]——i给大的吃}

d[i,j]=1 i=1andj=1

     1 i=0andj=0andm=2

     0 else

其中f[0,0,k]=0，f[o,j,k]=max j>0

实现时我们选用记忆化搜索的方式，以避免许多不必要的问题计算，问题至此就解决了。

题目总结：

这一题的关键在于对小头的转换，其他的只是一些顺理成章的问题。

注：这个是看算法艺术与信息学竞赛书写的，我自己还有另外一个想法，就是可以用邻接表做此题（也有可能就是线段树，目前我还不怎么明白线段树，所以不确定是个啥），就是把所有结点存在顶点表里，然后每个结点又有一个边表，把其所有直接子节点依次存里面（参考），及把某结点的所有直接子节点转换成线性的，然后用类似的方法做，要哪位大虾能明白或是有别的想法，请一定要留个贴哈，先在此谢谢啦。