题解 P6184 [USACO08OCT]Building A Fence G

分析

题意就是将给定的 \(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;
}

题解 P6184 [USACO08OCT]Building A Fence G

上一篇:简单的springmvc搭建


下一篇:数据结构之红黑树