UVA - 11401 - Triangle Counting（递推+找规律）
题目问，从长度1—n的木棍中选择若干条木棍，问能组成多少种三角形。
因为只能从1—n根木棍中选择3根，所以木棍的长度不能相同。
N的范围比较大，但我们发现这些问题之间有相似的地方。
比如说n=6的时候构成三角形的总数和n=5的时候构成三角形的总数，之间有联系。
只需要在之前的基础上加上一些边（考虑多一条6的情况）
通过找规律，发现每次需要加上cnt种情况，而cnt呈现规律。
+2 +2 +3 +3 +4 +4。。。这样就可以写出一个类似于动规的状态转移方程
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<functional>
#define ll long long
using namespace std;
ll dp[1000005];
int main()
{
ll n;
ll cnt;
ll i,j,k;
dp[4]=1;
cnt=2;
k=0; j=2;
for(i=5;i<=1000000;i++)
{
dp[i]=dp[i-1]+cnt;
k++;
cnt+=j;
if(k%2==0&&k!=0)
{
k=0;
j++;
}
}
while(scanf("%lld",&n)!=EOF)
{
if(n<3)
break;
else
printf("%lld\n",dp[n]);
}
}