It is said that dynamic progamme is OK,can anyone suply it?
Послано
yuwei 1 ноя 2004 18:38
my email: yuwei110@yahoo.com.cn
Re: It is said that dynamic progamme is OK,can anyone suply it?
Послано
nana 11 авг 2005 14:48
Please somebody explain me too, how to solve this problem.
Thank's!!!
my e-mail: r86acm@ukr.net
Edited by author 11.08.2005 14:49
Re: It is said that dynamic progamme is OK,can anyone suply it?
We can imagine that there's also a branch (or a trunk ^_^) below the root node, on which of course there are no apples at all. We denote by dp[x,y] the number of apples we can keep if we can keep y edges on the subtree with root x and the branch right below x.
If y=0, then dp[x,0]=0.
If y=1, then the branch right below x must be kept, so dp[x,1]=the number apples on the branch right below x.
If y>1, then you can use enumeration to determine how many apples to keep on the two subtrees of x. Let a and b be the two children of x, then dp[x,y]=max{dp[x,1]+dp[a,i]+dp[b,y-1-i]}.
The complexity is obviously O(n^3).
Good luck!
P.S. To Roman: I wonder why I can't send you e-mail from my Chinese mailbox. In the future you could send questions into this Japanese mailbox: akisame1988@yahoo.co.jp.
Re: It is said that dynamic progamme is OK,can anyone suply it?
Послано
nana 28 авг 2005 02:41
At last I solved that problem!
Edited by author 28.08.2005 02:42