bzoj1600 [Usaco2008 Oct]建造栅栏（排列组合）

勤奋的Farmer John想要建造一个四面的栅栏来关住牛们。他有一块长为n（4<=n<=2500）的木板，他想把这块本板切成4块。这四块小木板可以是任何一个长度只要Farmer John能够把它们围成一个合理的四边形。他能够切出多少种不同的合理方案。注意： *只要大木板的切割点不同就当成是不同的方案（像全排列那样），不要担心另外的特殊情况，go ahead。 *栅栏的面积要大于0. *输出保证答案在longint范围内。 *整块木板都要用完。

思路：排列组合。。减法原则。长度为n的木板，有n-1个切点，那么n-1个切点切三刀的方案数就是C(n-1,3) ，但是这里面有不能构成四边形的。

构成四边形的条件是：任意三边之和大于第四边。也就是任意a+b+c>d，可以得到d<n/2

为方便描述，我们不妨认为从左往右切，先且最左边，再切最右边。

并且先讨论最右边的木板是长度最长的。

所以我们最后一刀一定切在n/2之后的地方。

此时无论之前的两刀是怎么切的，由于切完出现的三块的长度和是一定的，所有都一定能构成四边形。

多算的部分就是从n/2点，最左边可以切到3点的方案数。

如果最后一刀切在点i,那么左边还剩下i-1个点，选两个点切，方案数为C(i-1,2)

将多切的方案数sad按照最后一刀的切点累加。

需要注意的是，我们之前为了方便讨论，设最后一个木板是最长的，然而实际上四块木板都有可能是最长的。所以多切的方案数sad=sad*4

哦，听说这题dp也能过。。。。？反正我是想不到。

 1/* ***********************************************
 2Author :111qqz
 3Created Time :2016年03月31日 星期四 18时23分16秒
 4File Name :code/bzoj/1600.cpp
 5************************************************ */
 6
 7#include <cstdio>
 8#include <cstring>
 9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int N = 2600;
34LL n;
35
36int main()
37{
38	#ifndef  ONLINE_JUDGE
39	freopen("code/in.txt","r",stdin);
40  #endif
41	cin>>n;
42	LL ans = (n-1)*(n-2)*(n-3)/6;
43	LL sad = 0LL;
44	for ( LL i =n/2  ; i >= 3 ; i--)
45	{
46	    sad = sad + ((i-1)*(i-2)/2)*4;  //C(i-1,2) ，*4是因为每个点都有可能作为最大点。
47	}
48//	cout<<"ans:"<<ans<<endl;
49//	cout<<"sad:"<<sad<<endl;
50	ans -=sad;
51	cout<<ans<<endl;
52
53
54  #ifndef ONLINE_JUDGE
55  fclose(stdin);
56  #endif
57    return 0;
58}

相关文章