题目链接：11401 - Triangle Counting
题意：有1,2,3....n的边，求最多能组成的三角形个数。 思路：利用三角形不等式，设最大边为x,那么y + z > x 得 x - y < z < x 然后y取取值，可以从1取到x - 1，y为n时候，有n - 1个解，那么总和为0 + 1 + 2 +...+ (x - 2) = (x - 1) * ( x- 2) / 2; 然后扣除掉重复的y = z的情况，在y > x / 2时，每个y取值会出现一次y = z. 然后在扣除掉一半y,z交换的相同情况。最后就是答案 得到递推式ans[i] = ans[i - 1] + ((i - 1) * (i - 2) / 2 - (i - 1) / 2) / 2; 代码：#include#include const int N = 1000005; int n; long long ans[N]; int main() { ans[3] = 0; for (long long i = 4; i <= 1000000; i++) { ans[i] = ans[i - 1] + ((i - 1) * (i - 2) / 2 - (i - 1) / 2) / 2; } while (~scanf("%d", &n) && n >= 3) { printf("%lld\n", ans[n]); } return 0; }