说好的今天开始刷水。。

本题一开始我以为是排列组合，但是自己弱想不出来，只想到了如果四边有一条边大于或等于第三边，那么这个四边形构造不出来。

即

a>=b+c+d时，不存在四边形

那么存在的情况就是a<b+c+d

得到

a<a+b+c+d

因为a<2a，a<b+c+d

所以a<(a+b+c+d)/2=n/2

那么我们就可以dp了。

只要找所有满足的边满足比长度的一半小就行了

设f[i, j]表示i块木板j长可以组成的四边形数

有f[i, j]=sum{ f[i-1, j-k] } 1<=k<=min(j, n/2-1)

k就代表了多出来的一边长为k

初始化f[0, 0]=1

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;#define rep(i, n) for(int i=0; i<(n); ++i)#define for1(i,a,n) for(int i=(a);i<=(n);++i)#define for2(i,a,n) for(int i=(a);i<(n);++i)#define for3(i,a,n) for(int i=(a);i>=(n);--i)#define for4(i,a,n) for(int i=(a);i>(n);--i)#define CC(i,a) memset(i,a,sizeof(i))#define read(a) a=getint()#define print(a) printf("%d", a)#define dbg(x) cout << #x << " = " << x << endl#define printarr(a, n, m) rep(aaa, n) { rep(bbb, m) cout << a[aaa][bbb]; cout << endl; }inline const int getint() { int r=0, k=1; char c=getchar(); for(; c<'0'||c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) r=r*10+c-'0'; return k*r; }inline const int max(const int &a, const int &b) { return a>b?a:b; }inline const int min(const int &a, const int &b) { return a
          
         
        
       
      
     

 

 

---

 

 

Description

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

Input

*第一行：一个数n

Output

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

Sample Input

6

Sample Output

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) – 不能够组成一个四边形.

HINT

Source