|
mining.in
|
mining.out
|
|
4 3
5 6 2 4 1 2 0 1 2 3 3 4 |
13
|
题目分析:
这道题的模型就是典型的树型DP.不知道大家是否看懂了题目,出题人蛤蟆本人觉得题意是清楚的,给了几位大牛们看了,都能理解题意.如果确实看不懂的也不要埋怨,NOIP2006提高组的第三题,就是一个典型,为了备战NOIP,请各位选手锻炼一下自己的阅读能力.
然后就从题目分析,题目中有句话说: 任意两点间有且只有一条路可通,也就是说这是一棵树,一棵以入口为根的树,这样数据结构就搞定了. ”每个人只能挖一个地方的宝藏”这句话说明每个人只能覆盖一个结点,那么M个就最多能覆盖M个结点.而且这M个点连成的也是一棵树.而且这棵树的所有结点的权和必须最大.这样一来我们最容易想到的就是动态规划.
算法分析:
题目中没准确说明这是一棵二叉树,所以这个宝藏应该是一棵多叉树.由于” 在每个分岔口,必须至少留一个人下来”这句话,说明要取一个点的子结点,就必须先取这个点.而取了这个点,总的M个人就会变成M-1个人,我们用f(i,j)表示取j个人到了第i个结点能够取到的最优值.f(0,m)就是答案.
但是如果直接DP一棵多叉树,是有问题的,(出题人太水,不会).所以我就先把多叉树转化为二叉树,按照左儿子右兄弟转化.就把一棵多叉树转化成二叉树了.然后这个问题就变得非常极其十分简单了.
方程:f(i,j):=max{max{f(tree[i].l,k)+f(tree[i].r,j-1-k)}(0<=k<=j-1),f(tree[i].r,j)}
数据分析:
数据给定的规模是N<=1000,M<=100,DP的时间复杂度和空间复杂度都是没问题的.一开始输入的一棵树,应该怎样存储?应该N<=1000,所以直接用邻接表是没问题,但如果N<=10000呢?(其实出题人本来是想出N<=10000,M<=100的,就算这样DP的时间复杂也不会有问题,但一开始多叉树的存储就可能会出问题)如果N=10000,那普通的邻接表显然会空间溢出,这里介绍一种压缩邻接表的存储方法,压缩邻接表就是一个一维的数据,外加一个N大的数组作标记,标记第i个结点从哪位开始,a[i+1]-1就是第i个结点结束的位置,这样空间就可以压缩了.10000个点都没问题.
大家看题时要看清,每个点的财富值是|wi|<maxint,也就是说会有负值出现.看不清也没什么大问题!
数据有点弱,有20分的数据是送的,这两个数据一个全是1,一个全是-1.还有第一个数据是N<10的小数据.