分析
题意就是将给定的 \(N\) 分为四块作为一个四边形的四条边长,因此可以得到一个信息,最大的一条边长最大必须小于 \(n\) 的一半(类比于三角形两边之和大于第三边),此前提下才能保证四条边能形成四边形。
想到 \(dp\),对于现在连接第 \(i\) 条边时,先枚举连出这条边后的总长度 \(j\),再去枚举本次我们要连接一条多长的边,令为 \(k\),因此新连上这条边后,\(dp(i,j)\) 就要加上上一条边连接后拥有的方案数,即加上 \(dp(i-1,j-k)\),至此此题得解,注意方案数仅有加计算,将 \(dp(0,0)\) 初始赋值为1即可。
代码
#include<bits/stdc++.h>
using namespace std;
int n,f[5][2555];
inline int min(int x,int y){
return x<y?x:y;
}
int main()
{
cin>>n;
f[0][0]=1;//初始化
for(int i=1;i<=4;i++){
for(int j=1;j<=n;j++){
for(int k=1;k<=min(j,(n-1/2));k++)//取最小,保证新加的边不会大于等于总长度的一半
f[i][j]+=f[i-1][j-k];//累计
}
}
cout<<f[4][n]<<endl;
return 0;
}