Uva：11401-Triangle Counting

Triangle Counting

Time limit1000 ms

Description

You are given n rods of length 1, 2…, n. You have to pick any 3 of them and build a triangle. How many distinct triangles can you make? Note that, two triangles will be considered different if they have at least 1 pair of arms with different length.

Input

The input for each case will have only a single positive integer n(1<=n<=1000000). The end of input will be indicated by a case with n<1. This case should not be processed.

Output

For each test case, print the number of distinct triangles you can make.

Simple Input

5
8
0

Simple Output

3
22

---

解题心得：

1. 刚开始看到题的时候以为是以前做过的一个dfs的三角形拼接，但是这个题问的是用从1到n长度的木棍来拼接，然后比较容易就可以看出是一个递推的问题，每增添一根木棍答案就会增加一部分，然后就是怎么递推了。
2. 这个递推的思想其实就是先算出所有能够选择的方案，然后减去重复的方案。从第一条边开始看有多少种方案，会发现是0+1+2+…..（x-2） = （x-1）*（x-2）/2。但是里面包含了不符合要求的，不符合要求的（两边之和不大于第三边）数量（n-1）/2，另外还有重复的，每个符合条件的情况算了两次（从前往后依次，从后往前一次），还要除2。
3. 还可以按照组合数学来算，但是这样也挺麻烦的，好像还可以寻找循环节。

---

#include<stdio.h>
#include<iostream>
#include<queue>
#include<cstring>
#include<map>
#include<algorithm>
#include<stack>
using namespace std;
const int maxn = 1000010;
typedef long long ll;
ll f[maxn];
void pre_deal()
{
    for(long long  i=4;i<maxn;i++)
    {
        ll k = ((ll)(i-1)*(ll)(i-2)/2-(ll)(i-1)/2)/2;
        f[i]=f[i-1]+k;
    }
}
int main()
{
    memset(f,0,sizeof(f));
    ll n;
    pre_deal();
    while(scanf("%lld",&n))
    {
        if(n<3)
            break;
        printf("%lld
",f[n]);
    }
    return 0;
}