uva 11401 - Triangle Counting

題目出處：Uva

題目連結：11401 - Triangle Counting

題目大意：link(luckycat)

解題方法：透過dynamic programming的方法，若要討論使用1~N的邊，則會是使用1~N-1的情況加上有使用N的情況(當然此時，N會是最大邊)。
以N = 10為例子。三條邊可以為（由左至右是由小到大）：
邊a 邊b 邊c 幾種組合
2~8  9  10      7
3~7  8  10      5
4~6  7  10      3
5~5  6  10      1
因此，以邊長10為最大邊的情況，可以透過等差級數(S)去計算。 
S = a1 + (a1+d) + (a1+2*d) + ... + (a1+(n-1)*d)
= a1*n + ((n-1)+0)*(n)/2*d
= a1*n + (n-1)*n/2*(-2)
= a1*n - (n-1)*n
= n*(a1-n+1)
a1是首項(N-3)，d是公差(-2)，n是數量((a1+1)/2)。
因此，dp[i] = dp[i-1] + S

注　　意：需要化簡，過程中才不會overflow。

代碼如下：