描述 Description
勤奋的 Farmer John 想要建造一个四面的栅栏来关住牛们。他有一块长为 n（4<=n<=2500）的木板，他想把这块本板切成 4 块。这四块小木板可以是任何一个长度只要 Farmer John 能够把它们围成一个合理的四边形。他能够切出多少种不同的合理方案。注意： * 只要大木板的切割点不同就当成是不同的方案（像全排列那样），不要担心另外的特殊情况，go ahead。 * 栅栏的面积要大于 0. * 输出保证答案在 longint 范围内。 * 整块木板都要用完。
输入格式 InputFormat
第一行：一个数 n.
输出格式 OutputFormat
第一行：合理的方案总数。
样例输入 SampleInput
2500
样例输出 SampleOutput
1298961249
来源 Source
资格赛
代码 Code
f[i][j] 表示用 i 条边组成周长为 j 的四边形的方案数。
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
long long f[5][2505];
int i,j,t,n,m,l,r,k,z,y,x;
int main()
{
scanf("%d",&n);
f[0][0]=1;
if (n%2==0) m=n/2-1;
else m=n/2;
for (i=1;i<=4;i++)
{
for (j=1;j<=n;j++)
{
for (k=1;k<=m;k++) if (j>=k)
{
f[i][j]+=f[i-1][j-k];
}
}
}
printf("%dn",f[4][n]);
return 0;
}