给出一个数字n，计算从1到n能组成几个不同的三角形。
n的范围是10^6，大概就是递推吧。从F[i-1]到F[i]可以线性求出。要注意结果超出int。
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; long long dp[1000100]; int N; int main() { dp[3] = 0; dp[4] = 1; dp[5] = 3; for(int i=6;i<1000010;i++) { long long k = i-3; if(k&1) dp[i] = dp[i-1]+(k+1)*(k+1)/4; else dp[i] = dp[i-1]+ k*(k+2)/4; } while(~scanf("%d",&N) && N>=3) { printf("%lld\n",dp[N]); } }
原文：http://www.cnblogs.com/helica/p/5170272.html