joj 1026解題報告

 1026: The Staircases

Result	TIME Limit	MEMORY Limit	Run Times	AC Times	JUDGE
	3s	8192K	1590	530	Standard

One curious child has a set of N little bricks. From these bricks he builds different staircases. Staircase consists of steps of different sizes in a strictly descending order. It is not allowed for staircase to have steps equal sizes. Every staircase consists of at least two steps and each step contains at least one brick. Picture gives examples of staircase for N=11 and N=5:

Your task is to write a program that reads from input numbers N and writes to output numbers Q - amount of different staircases that can be built from exactly N bricks.

Input

Numbers N, one on each line. You can assume N is between 3 and 500, both inclusive. A number 0 indicates the end of input.

Output

Numbers Q, one on each line.

Sample Input

3
5
0
      

Sample Output

1
2
      

這道題可以用動态規劃群組合數學的思想，這裡隻說組合數學的思想，主要就是母函數的思想，輸入N，那麼此時有N個磚塊來組成樓梯，我個人了解其實就是把樓梯可以分解成n個有不同磚塊數目組成的長方形和正方形，如圖中N=5時，有兩種分解方法，第一種是分解為一個磚頭組成的正方形，和四個方塊組成的長方形，第二種是将其分解為一個磚頭組成的正方形和四個磚塊組成的長方形。并且每輸入一個N，那麼一定可以按照這種方法分解，那麼這個道題就可以變成一道組合計數的問題，進而可以想到用母函數的思想來解決，(1+x^1)(1+x^2).....(1+x^N),算出x^N項的系數，然後再減1，即為所求的解，例如，當N=5的時候，(1+x^1)(1+x^2)(1+x^3)(1+x^4)(1+x^5)，求出x^5的系數為3，x^5=1(x^0)*x^5=x^1*x4=x^2*x^3，而第一種1*x^5是不符合情況的，因為，這種相當于隻有一個由5個磚塊組成的長方形，想象一下，這就是1個樓梯，不符合題意，是以要将這個情況減去。 代碼： 語言：c++ #include<iostream>

#include<cstdio>

using namespace std;

int main()

{

int i,j,n;

double ans[510]={1,1};//已經把ans[1]和ans[0]賦為1了，其餘為0

for(i=2;i<=500;i++) //構造母函數

{

for(j=500;j>=0;j--)

{

if(i+j<=500) ans[i+j]+=ans[j];

}

}

while(cin>>n)

{

if(n==0)

break;

printf("%.0lf/n",ans[n]-1);

}

return 0;

}