[Usaco2008 Oct]建造栅栏

[Usaco2008 Oct]建造栅栏

Time Limit:5000MS Memory Limit:65536K
Total Submit:6 Accepted:6
Case Time Limit:1000MS

Description

勤奋的Farmer John想要建造一个四面的栅栏来关住牛们。他有一块长为n(4<=n<=2500)的木板,他想把这块本板切成4块。
这四块小木板可以是任何一个长度只要Farmer John能够把它们围成一个合理的四边形。他能够切出多少种不同的合理方案。
注意:

*只要大木板的切割点不同就当成是不同的方案(像全排列那样),不要担心另外的特殊情况,go ahead。

*栅栏的面积要大于0.

*输出保证答案在longint范围内。

*整块木板都要用完。

Input

*第一行:一个数n

Output

*第一行:合理的方案总数

Sample Input

Sample Output

Source

资格赛
饿。。这个本来是要用Dp的。。但我容斥用爽了。。直接上容斥原理(*^__^*)
Code:

#include<iostream>#include<cstdio>#include<algorithm>#include<cmath>#include<cstdlib>#include<cstdlib>#include<cstring>#include<string>#include<vector>#include<set>#include<queue>#include<map>#define rep(i,n) for(int i=0;i<n;i++)#define For(i,a,b) for(int i=a;i<=b;i++)#define tr(i,x) for(typeof(x.begin()) i=x.begin();i!=x.end();i++)#define all(x) x.begin(),x.end()#define pb push_backusing namespace std;const int inf=~0U>>1,maxn=2600;typedef vector<int> vi;typedef vector<vi> vvi;typedef pair<int,int> ii;int n,dp[5][maxn]={0};typedef long long ll;ll WaySumTo(int a,int b){ if(a<0)return 0; ll ret=1;a+=–b; rep(i,b) ret*=a-i; rep(i,b) ret/=i+1; return ret;}int main(){ //freopen("in","r",stdin); cin>>n;int a=n/2;if(a*2==n)–a; n-=4; cout<<WaySumTo(n,4)-4*WaySumTo(n-a,4)+6*WaySumTo(n-2*a,4)-4*WaySumTo(n-3*a,4)+WaySumTo(n-4*a,4)<<endl;}

6输出详解:Farmer John能够切出所有的情况为: (1, 1, 1,3); (1, 1, 2, 2); (1, 1, 3, 1); (1, 2, 1, 2); (1, 2, 2, 1); (1, 3,1, 1);(2, 1, 1, 2); (2, 1, 2, 1); (2, 2, 1, 1); or (3, 1, 1, 1).下面四种 — (1, 1, 1, 3), (1, 1, 3, 1), (1, 3, 1, 1), and (3,1, 1, 1) – 不能够组成一个四边形.6

2 thoughts on “[Usaco2008 Oct]建造栅栏

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>