題目大意：給出n條線段，長度為1-n，問有多少種方法可以從這n條線段中取出3條不同的線段，使得以它們?yōu)槿呴L可以組成三角形。

分析：首先想到的方法就是三重循環(huán)枚舉，但是時間復雜度為O(n^3)，肯定超時。數(shù)據(jù)規(guī)模即使是O(n^2)時間的算法都很難承受，所以要進行數(shù)學分析。

設(shè)最大邊長為x的三角形有C(x)個，另外兩條邊長分別為y和z，根據(jù)三角不等式有y+z>x。所以z的范圍是x-y < z < x。

根據(jù)這個不等式，當y=1時x-1 < z < x,無解；y=2時有一個解（z=x-1）；y=3時有兩個解（z=x-1或者z=x-2）……直到y(tǒng)=x-1時有x-2個解。根據(jù)等差數(shù)列求和公式，一共有0+1+2+……+（x-3）+ （x-2） = (x-1)(x-2)/2個解。

可這并不是C(x)的正確值，因為上面的解包含了y=z的情況，而且每個三角形算了兩遍。所以要統(tǒng)計出y=z的情況。y的取值從x/2+1開始到x-1為止，一共有(x-1) - (x/2+1) + 1 = x/2 - 1個，但是我們不難發(fā)現(xiàn)，當x為奇數(shù)時，y的取值為x/2個；x為偶數(shù)時，y的取值為x/2-1個。所以為了避免討論x的奇偶性，我們把x/2-1寫成(x-1)/2就可以了，而且不影響正確結(jié)果。把這分解扣除，然后在除以2，即C(x)=((x-1)(x-2)/2 - (x-1)/2)/2;原題要求的是"最大邊長不超過n的三角形數(shù)目F(n)",則F(n)=C(1)+C(2)+…+C(n)。寫成遞推式就是F(n) = F(n-1) + C(n)。