|
|
back to boardVery easy dp problem! AC code Posted by MSDN 2 Feb 2008 22:06 #include <stdio.h> void main() { int N,i,j; scanf("%d",&N); double **F=new double*[N]; for(i=0;i<N;i++) { F[i]=new double[N]; for(j=0;j<N;j++) F[i][j]=0; F[i][i]=1; } for(i=1;i<N;i++) for(j=i-1;j>=0;j--) F[i][j]=F[i-j-1][j+1]+F[i][j+1]; printf("%.0lf",F[N-1][0]-1); } Re: Very easy dp problem! AC code Can you explain what do elements of your matrix keep? Re: Very easy dp problem! AC code Can u explain, or give where I can read about this task? Re: Very easy dp problem! AC code Posted by MSDN 19 Sep 2008 11:03 Let's designate height of a step i for ai then we need to find all such sets 0 <a1 <a2 <... <ai and a1+a2 +... +ai=N. That is it is necessary to count quantity of splittings of number N on decreasing composed. F[i][j] is a quantity of splittings of number i on composed not less j. Then the formula is fair F[i][j] =F[i-j][j+1] + F[i][j+1] F[i-j][j+1] - the number j participates in splitting F[i][j+1] - does not participate P.S. Sorry for my English Edited by author 19.09.2008 11:04 |
|
|