DragonSon's blog

By DragonSon, 14 years ago, In English
Hello

can any one please explain problem D ..... i tried to solve it using DP but I dont know why my code make wrong answers

thanks
  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
What integer type do you use? long long? What is output method? prinf("%lld\n", result)?
14 years ago, # |
  Vote: I like it +2 Vote: I do not like it
I used DP as main idea and the inclusion–exclusion principle to count only trees not higher than h. So I didn't need ignore parameter and had no troubles with this problem. My code:

#define LL long long
#define
FI(i,a) for (int i=0; i<(a); ++i)

LL R
( LL n, LL h)
{

       
if (m[n][40+h]!=-1) return m[n][40+h];
       
if (n==0)
       
{
               
if (h>0) return 0;
               
else return 1;
       
}
       LL res
=0;
       FI
(i,n)
                res
+=R(i,h-1)*R(n-i-1,0)+R(i,0)*R(n-i-1,h-1)-R(i,h-1)*R(n-i-1,h-1);
      
return m[n][40+h]=res;
}

14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
And sorry once again, there had to be "higher than h-1" instead of "not higher than h"