这道题主要是得算出第n年出生的母牛数量，可以由题目推出递推公式，第n年出生的母牛来自第n-1年的牛和n-3年刚出生的小母牛成熟后所生的数量之和。下面是实现的关键代码：

int f(int a)

{

if(a<=4&&a>0)return 1;

else return f(a-3)+f(a-1);

}

在做递归递推的时候，第一大关是得出递推递归公式，第二大关也是最容易忽略的地方就是超时问题，在需要多次递归的时候，有时候就会遇到超时的问题，而这种问题，需要做一些记忆化搜索就能避免超时。下面是一个简单的例题：

给定一个函数 f(a, b, c)：

如果 a ≤ 0 或 b ≤ 0 或 c ≤ 0 返回值为 1；

如果 a > 20 或 b > 20 或 c > 20 返回值为 f(20, 20, 20)；

如果 a < b 并且 b < c 返回 f(a, b, c?1) + f(a, b?1, c?1) ? f(a, b?1, c)；

其它情况返回 f(a?1, b, c) + f(a?1, b?1, c) + f(a?1, b, c?1) ? f(a-1, b-1, c-1)。

其他没有什么特殊的地方，就是要注意一个记忆化搜索：

int f(int a,int b,int c)

{

if(a<=0||b<=0||c<=0)return 1;

else if(a>20||b>20||c>20)return f(20,20,20);

if(m[a][b][c]==0)//判断是否已经计算过这里的函数值，若计算过则直接输出，未计算则进行计算。

{

if(a

else return m[a][b][c]=f(a-1,b,c)+f(a-1,b-1,c)+f(a-1,b,c-1)-f(a-1,b-1,c-1);

}

else return m[a][b][c];

}

2.3 动态规划

第一次学ACM程序设计感到困难的第一大关就是动态规划，动态规划是解决多阶段决策问题的一种方法。多阶段决策问题就是如果一类问题的求解过程可以分为若干个互相联系的阶段，在每一个阶段都须作出决策，并影响到下一个阶段的决策。多阶段决策问题，就是要在可以选择的那些策略中间，选取一个最优策略，使在预定的标准下达到最好的效果。动态规划遵从一个最优性原理，不论初始状态和第一步决策是什么，余下的决策相对于前一次决策所产生的新状态，构成一个最优决策序列。最优决策序列的子序列，一定是局部最优决策子序列。包含有非局部最优的决策子序列，一定不是最优决策序列。

动态规划的指导思想是在做出每一步决策时，列出各种可能的局部解，然后依据某种判定条件，舍弃那些肯定不能得到最优解的局部解，并且以每一步都是最优的来保证全局是最优的。

动态规划与递归递推有些相似，但是动态规划多了一个要求，要求做最优的选择，在每次递推中选择最优的状态。动态规划问题的一般解题步骤分为六步：

1、判断问题是否具有最优子结构性质，若不具备则不能用动态规划。

2、把问题分成若干个子问题（分阶段）。

3、建立状态转移方程（递推公式）。

4、找出边界条件。

5、将已知边界值带入方程。

6、递推求解。

例如virtual judge上动态规划的一道最长上升子序列的问题：一个数的序列bi，当b1 < b2 < ... < bS的时候，我们称这个序列是上升的。对于给定的一个序列(a1, a2, ..., aN)，我们可以得到一些上升的子序列(ai1, ai2, ..., aiK)，这里1 <= i1 < i2 < ... < iK <= N。比如，对于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。这些子序列中最长的长度是4，比如子序列(1, 3, 5, 8)。我们的任务，就是对于给定的序列，求出最长上升子序列的长度。

如何把这个问题分解成子问题呢？经过分析，发现“求以ak（k=1,2, 3…N）为终点的最长上升子序列的长度”是个好的子问题。

由上所述的子问题只和一个变量相关，就是数字的位置。因此序列中数的位置k就是“状态”，而状态k对应的“值”，就是以ak做为“终点”的最长上升子序列的长度。这个问题的状态一共有N个。状态定义出来后，转移方程就不难想了。

假定MaxLen (k)表示以ak 做为“终点”的最长上升子序列的长度，那么：MaxLen (1) = 1，MaxLen (k) = Max { MaxLen (i)：1

下面是实现动态规划的代码：

int i,j,N;

cin>>N;

int b[N+1],aMaxLen[N+1];

for(i=1;i<=N;i++)

{

cin>>b[i];

}

aMaxLen[1]=1;

for(i=2;i<=N;i++)//求以第i个数为终点的最长上升子序列的长度

{

int nTmp=0;//记录第i个数左边子序列最大长度

for(j=1;j

{

if(b[i]>b[j])

{

if(nTmp

}

}

aMaxLen[i]=nTmp+1;

}

int nMax=-1;

for(i=1;i<=N;i++)

{

if(nMax

}

cout<

2.4 二分三分查找算法

二分查找算法的简单定义：在一个单调有序的集合中查找元素，每次将集合分为左右两部分，判断解在哪个部分中并调整集合上下界，重复直到找到目标元素。使用二分查找法非常关键的一点是一个单调有序的集合，若不是单调有序，则需想办法转化成单调有序的，这个二分查找法的花费时间优于直接按顺序查找，实际使用的时候，则需将问题所指的东西即答案，如果答案具有特定的范围，并且验证答案是否成立的函数具有单调性。则可以在范围内对答案进行二分查找，从而快速确定答案。

这个专题，由于初高中介绍过类似的数学思想，在接受起来比动态规划要好很多，在二分贪心中的一个题目十分的经典：

Farmer John has built a new long barn, with N (2 <= N <= 100,000) stalls. The stalls are located along a straight line at positions x1,...,xN (0 <= xi <= 1,000,000,000).

His C (2 <= C <= N) cows don't like this barn layout and become aggressive towards each other once put into a stall. To prevent the cows from hurting each other, FJ want to assign the cows to the stalls, such that the minimum distance between any two of them is as large as possible. What is the largest minimum distance?