一看就是一個(gè)遞推的題目，自己推了一會(huì)兒，推出來(lái)一個(gè)遞推公式，有點(diǎn)搓
F[i][j]，表示的是第一個(gè)的樓梯高度是i的情況下，用j塊積木的堆積方案
結(jié)果發(fā)現(xiàn)好像要用O(n^3)的時(shí)間復(fù)雜度才能解決，不過(guò)好在這個(gè)遞推公式對(duì)了
但是怎么都WA，自己驗(yàn)證了幾組比較小的數(shù)據(jù)，都對(duì)了
然后只能去Google一下，后來(lái)發(fā)現(xiàn)有個(gè)人說(shuō)，這道題目有大數(shù)陷阱，用double就過(guò)了
一試，沒(méi)過(guò)-_-!!!，懷疑自己的地推公式對(duì)不對(duì)……
后來(lái)想了想，是不是我的輸出有問(wèn)題，原來(lái)是cout << sum <<ｅｎｄｌ；
改成了ｐｒｉｎｔｆ（＂％０．０ｌｆ＼ｎ＂，ｓｕｍ）；
ＡＣ了，很神奇……
為什么在我自己的電腦上面，運(yùn)算出來(lái)的結(jié)果顯示的都是整數(shù)呢……，非得用個(gè)０．０ｌｆ這種東西才能過(guò)
看來(lái)還是對(duì)ｇｃｃ不了解……

 1 #include <iostream>
 2 
 3 using namespace std;
 4 
 5 double F[505][505];
 6 
 7 int main()
 8 {
 9 
10     for (int i = 1; i < 505; i++)
11         for (int j = 1; j < 505; j++)
12         {
13             if (i!=j)
14                 F[i][j] = 0;
15             else
16                 F[i][j] = 1;
17         }
18 
19     for (int i = 3; i < 505; i++)
20         for (int j = 1; j <= (i-1)/2; j++)
21             for (int k = j + 1; k <= i - 1; k++)
22                     F[j][i] += F[k][i-j];
23 
24     int N;
25     while (cin >> N && N!=0)
26     {
27         double sum = 0.0;
28         for (int i = 1; i <= (N-1)/2;i++)
29             sum+=F[i][N];        
30         printf("%0.0lf\n",sum);
31     }
32 
33     return 0;
34 }
35