uva11401：Triangle Counting 递推 数学

　　uva11401：Triangle Counting

题目读不清楚的下场就是多做两个小时...从1-n中任选3个不重复数字（不重复啊！！坑爹啊！）问能组成三角形的有多少个，

显然1~n能组成的三角形集合肯定包括了1~n-1所能组成的三角形，所以假如have[i-1]为1~n-1组成的三角形数目，have[i]只要计算：含有长度为n的边的三角形数目+have[i-1] 就行了

然后分一下类就行了，1~n/2为一块，n/2+1~n为一块，因为有一条边必须为n，剩下两条边要么都在第二块，要么分别在第一第二块，在把n分奇偶讨论下很容易就得到公式了

#include <iostream>
#include <string.h>
#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>
#include <algorithm>
#include <math.h>

#define SIGMA_SIZE 26
#pragma warning ( disable : 4996 )

using namespace std;
typedef long long LL;
//typedef unsigned long long uLL;

inline LL LMax(LL a,LL b)    { return a>b?a:b; }
inline LL LMin(LL a,LL b)    { return a>b?b:a; }
inline int Max(int a,int b) { return a>b?a:b; }
inline int Min(int a,int b) { return a>b?b:a; }
inline int gcd( int a, int b ) { return b==0?a:gcd(b,a%b); }
inline int lcm( int a, int b ) { return a/gcd(a,b)*b; }  //a*b = gcd*lcm
const long long INF = 0x3f3f3f3f3f3f3f3f;
const int inf  = 0x3f3f3f3f;
const int mod  = 7;
const int maxk = 5005;
const int maxn = 1e6+5;

int num[maxn];
LL have[maxn];

void init()
{
    //have[1] = 1; have[2] = 2;
    bool test = true;            //true表示奇数，false表示偶数
    
    have[3] = 0;
    LL tmp;
    for ( LL i = 4; i <= (LL)1e6; i++ )
    {
        LL t = i/2;
        if (!test)
        {
            have[i] = t*(t-1) + have[i-1];
            test = !test;
        }
        else
        {
            have[i] =  (t-1)*(t-1) + have[i-1];
            test = !test;
        }
    }
}

int main()
{
    init();

    int x;
    
    while ( ~scanf("%d", &x) && x >= 3 )
        printf( "%lld
", have[x] );
    return 0;
}