找三角形(递推)

UVA 11401

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2396

题解：求从1到n这些数字可以构成的三角形的个数。

假设现在的数是x，在它前面找两个数满足三角形定义的y和z，则有x - y < z < x。

当y = 1时，没有数z满足x - 1 < z < x，三角形个数num为 0；

当y = 2时，有1个z满足 x - 2 < z < x， num = 1;

y = 3,? num = 2;

······

y = x - 1,num = x - 2;

总的可以构成的三角形的个数为一个等差数列，N = (x - 2) *(x - 1) / 2;

但是！注意，在这些三角形中，包含了y == z的情况以及每个三角形都计算了两遍(这个问题只要结果除以2就解决了，关键是找到 y== z的情况)；

y的值从x / 2 + 1开始到x - 1有(x - 1) - (x / 2 + 1)? + 1 = x / 2 - 1 个解，当x为奇数时解为 x / 2， 偶数时解为x / 2 - 1，所以为了避免判断奇偶，我们把它写成(x - 1) / 2 就好了。

代码：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<stack>
#define ll long long
using namespace std;

const ll N = 1000005;
const ll maxn = 1e18;
const int inf = 1e9;

ll a[1000010];

int main()
{
    a[3] = 0;//预处理 
    for(ll i = 4; i <= 1000000; i++)
        a[i] = a[i-1] + ((i-1)*(i-2)/2 - (i-1)/2) / 2;
        
    int n;
    while((scanf("%d",&n)) != EOF && n >= 3)//注意此处必须n >= 3才能过，n != 0过不了
    {
        printf("%lldn",a[n]);
    }
    return 0;
}