输出格式：
输出n的所有k上升段的个数。
样例kink.in32
kink.out4
（说明，符合条件的排列是１３２，３１２，２１３，２３１）
解析：
本题看似要用回溯或组合数学来计算，但是它却确确实实只能用递推来做!
先给出递推式：
f（n,k）=（n-k）×f（n-1,k-1）+k×f（n-1,k）
形成f（n,k）的由两部分组成：
第一部分是f（n-1,k-1）变化而来，例如13254是一种f（5,3）,在每一个不是上升段的结尾处放上“6”都可以变成k个上升段，不是上升段的结尾处共有（（n－1）＋1）－k=n－k个;
第二部分是f（n-1,k）是变化而来，例如13542是一种f（5,4）,在每一个是上升段的结尾处放上“6”都可以保持k个上升段，是上升段的结尾处共有k个。
因此就有了上面的式子，只要递推即可，注意使用高精度。
递推要求数据关系较密切，有明确的公式和单调性，也就因此用途比较狭窄，但是绝不意味这在竞赛中没有用处，下面的例子就是一个很好的例子：
专题问题：
递推与动态规划的关系怎样？
递推没有重复计算什么数据，保持了高效。
让我们想到了动态规划（DP），动态规划与递推很相似，我认为：
动态规划＝递推＋贪心
大多数的动态规划的状态转移式是A[i,j]=max/min{A[k,l]|k满足条件E1,l满足条件E2}+date
明显的：
max/min就是贪心,而所谓的状态转移就是递推。
所以我个人认为DP就是递推时取了最优值罢了。
当然，DP要复杂的多，可以引申出好多内容和问题，没那么简单。
可转过来说，递推、贪心就没有很难的吗？
个人之见。
专题问题：
递推与递归的关系怎样？
递推的优点在哪儿？
递归与递推表面看来是相逆的过程，其实也是相似的，最终的计算都是从小算到大。
就是递推的使用环境要求高导致了递推的高效性，递推没有重复计算什么数据，保持了高效。
递归大多数会重复计算子问题，导致时间浪费，所以一般不要使用过深的递归，甚至会空间溢出。
但是也不能说递推好，递归差，因为递归却能解决很多递推做不到的事情，在某些特定的环境下也能实现高效，并且递归容易使用。
我们要就事论事！
对于递归和递推的效率问题，一般认为递推比递归优，举一个简单的例子:
最简单的斐波那契数列（Fibonacci），对于f（30），如果使用递归则需要运行1664079次，而递推只需30次就可以了，速度悬殊。
递归：
functionf（n:
longint）:
longint;
begin
ifi<3thenexit
（1）;
f:
=f（i-1）+f（i-2）;
end;
递推：
f[1]:
=1;f[2]:
=1;
fori:
=1ton-2do
begin
f[i+2]:
=f[i]+f[i+1];
end;
一般来说，递归需要有边界条件、递归前进段和递归返回段。
当边界条件不满足时，递归前进；当边界条件满足时，递归返回。
在考虑使用递归算法编写程序时，应满足两点：
1）该问题能够被递归形式描述；
2）是否存在递归结束的边界条件。
只有当这两者都满足时才可以使用递归算法。
递归的能力在于用有限的语句来定义对象的无限集合。
用递归思想写出的程序往往十分简洁易懂。
递归的应用范围很广：
1.经典递归
例如Hanoi塔问题：
经典的递归，原问题包含子问题。
有些问题或者数据结构本来就是递归描述的，用递归做很自然。
2.递归与递推，数学式关系
利用递归的思想建立递推关系，如由兔子生崽而来的fibonacci数列。
但递推由于没有返回段，因此更为简单，有时可以直接用循环实现。
3.分治等以大化小算法
不少分治方法是源于递归思想，或是递归分解+合并处理。
4.回溯
规模较小的问题用回溯解决比较自然。
注意递归前后要保证现场的保存和恢复，即正确的转化问题。
5.动态规划
动态规划的子问题重叠性质与递归有某种相似之处。
递归+动态修改查表是一种不错的建立动态规划模型的方法。
6.树、图、排序等符合递归子问题思想的结构
树、图等数据结构本身就是递归结构，因此当然是使用递归来处理。
7.其他
其他者，不好归类也。
例如表达式处理，排列组合等，很杂的。
例题2给出一棵二叉树的中序与后序排列。
求出它的先序排列。
分析通过对比二叉树的中序与后序排列，我们可以找出根节点及左右子树。
同样的，有可以通过对比左子树的中序与后序排列，找出左子树的根节点……可见，该问题能够被递归描述。
当找到最后一个根节点时，递归无法再进行下去，这就是递归结束的边界条件。
由此可见，递归算法中常常隐含了分治思想。
程序略。
例题3求把一个整数n无序划分成k份互不相同的正整数之和的方法总数。
分析这是一道动态规划题，动态方程如下：
f[i-1,j]+f[i,j-i]+1（（jmodi=0）and（jdivi=1））
f[i,j]:
=f[i-1,j]（i>=j）
f[i-1,j]+f[i,j-i]（else）
s:
=f（k,n-k）
本题可以用循环来实现递推,也可以考虑用递归求解。
主过程见下一页：
可以看出，方案一的程序较为冗长，消耗栈空间较大；而方案二较为简洁明了，所用的栈空间也较小，效率较高。
因此，使用递归算法也有一个优化问题。
算法的简洁与否直接制约了程序的可行性和效率。
方案一：
Procedurework（I,j:
longint;vars:
longint）;
Vart:
longint;
Begin
If（i=1）or（j=1）thens:
=1
Elseif（i=0）or（j=0）thens:
=0
Elsebegin
if（jmodi=0）and（jdivi=1）then
begin
work（i-1,j,s）;
t:
=s;
work（i,j-1,s）;
s:
=s+t+1;
end
elseif（i>=j）then
work（i-1,j）
elsebegin
work（i-1,j,s）;
t:
=s;
work（I,j-1,s）;
s:
=s+t;
end;
End;
方案二：
proceduresearch（v,w,last:
byte）;
vari:
byte;
begin
ifw=0theninc（count）
else
ifw=1then
ifv>=lastthensearch（0,0,0）else
elsefori:
=lasttov-1dosearch（v-i,w-1,i）;
end;
递归使一些复杂的问题处理起来简单明了，尤其在学习算法设计、数据结构时更能体会到这一点。
但是，递归在每一次执行时都要为局部变量、返回地址分配栈空间，这就降低了运行效率，也限制了递归的深度。
因此，在必要的时候可以只使用递归的思想来求解，而程序则转用非递归的方式书写，关于递归与非递归的转化，参见新高级本吧。
专题问题：
栈
（对不起，这里使用了一点别人的冬冬，第1节概述是我找的资料，其他是我自己的）
1．概述
栈（Stack）是一种特殊的线性表。
我们常举的例子是：
可以把食堂里冼净的一摞碗看作一个栈。
在通常情况下，最先冼净的碗总是放在最底下，后冼净的碗总是摞在最顶上。
而在使用时，却是从顶上拿取，也就是说，后冼的先取用，后摞上的先取用。
好果我们把冼净的碗“摞上”称为进栈，把“取用碗”称为出栈，那么，上例的特点是：
后进栈的先出栈。
然而，摞起来的碗实际上是一个表，只不过“进栈”和“出栈”，或者说，元素的插入和删除是在表的一端进行而已。
一般而言，栈是一个线性表，其所有的插入和删除均是限定在表的一端进行，允许插入和删除的一端称栈顶（Top），不允许插入和删除的一端称栈底（Bottom）。
若给定一个栈S=（a1,a2，a3，…，an），则称a1为栈底元素，an为栈顶元素，元素ai位于元素ai-1之上。
栈中元素按a1,a2，a3，…，an的次序进栈，如果从这个栈中取出所有的元素，则出栈次序为an,an-1，…，a1。
也就是说，栈中元素的进出是按后进先出的原则进行，这是栈结构的重要特征。
因此栈又称为后进先出（LIFO—LastInFirstOut）表。
我们常用一个图来形象地表示栈，其形式如右图：
通常，对栈进行的运算主要有以下几种：
（1）往栈顶加入一个新元素，称进栈；
（2）删除栈顶元素，称退栈；
（3）查看当前的栈顶元素，称出栈。
此外，在使用栈之前，首先需要建立一个空栈，称建栈；在使用栈的过程中，还要不断测试栈是否为空或已满，称为测试栈。
2．栈的存储结构
栈是一种线性表，在计算机中用向量作为栈的存储结构最为简单。
因此，当用编程语言写程序时，用一维数组来建栈十分方便。
例如，设一维数组STACK[1..n]表示一个栈，其中n为栈的容量，即可存放元素的最大个数。
栈的第一个元素，或称栈底元素，是存放在STACK[1]处，第二个元素存放在STACK[2]处，第i个元素存放在STACK[i]处。
另外，由于栈顶元素经常变动，需要设置一个指针变量top，用来指示栈顶当前位置，栈中没有元素即栈空时，令top=0，当top=n时，表示栈满。
3．“栈”在递归、回溯中的作用？
栈是事实上的递归、回溯使用方法，我们使用递归时就是利用了栈的原理：
每一层保存当前的状态，然后继续递归到下一层。
当我们理解了栈的使用与递归后，我们可以使用模拟的栈（以我们自己的原则，创建一个栈，并由我们自己来维护）来实现所有的递归、回溯问题，尽管使用递归很简洁方便，但是对于大型程序、层数众多的程序，我们需要模拟栈来实现。
模拟栈实现回溯的就叫做模拟回溯。
栈的表象，《数据结构》的演示程序十分真切的，我就不想冗述^-^我截了两幅图，在这里代替了。
栈溢出是递归、回溯使用时的大问题，特别是对于数据大的题目，我们应当特别注意。
四、回溯·递推·递归运用与优化
在本节主要是回溯、递推、递归的深入讨论和优化。
下面对一个经典问题做一下讨论：
八皇后之递归算法、回溯算法
我在网上偶尔找到了一个N皇后的演示程序，做的非常好，大家共享，共同进步。
【问题描述】在一个８×８格子的棋盘上，要布局八个皇后，条件是不能出现两个皇后在同一行或同一列或同一斜线的情况，以防“相互攻击”，请问共有多少种合理的布局方式，每一种布局的具体情况如何？
右上图是4皇后问题规则示意
右下图是8皇后问题的第一个解
【分析】显然问题的键在于如何判定某个皇后所在的行、列、斜线上是否有别的皇后；可以从矩阵的特点上找到规律，如果在同一行，则行号相同；如果在同一列上，则列号相同；如果同在／斜线上的行列值之和相同；如果同在＼斜线上的行列值之差相同；如果斜线不分方向，则同一斜线上两皇后的行号之差的绝对值与列号之差的绝对值相同。
从下图可以验证上面的说法：
对于一组布局我们可以用一个一维数组来表示：
X:
ARRAY[1..8]OFINTEGER;X[I]的下标I表示第I个皇后在棋盘的第I行，X[I]的内容表示在第I行的第X[I]列，例如：
X[3]=5就表示第3个皇后在第3行的第5列。
在这种方式下，要表示两个皇后A和B不在同一列或斜线上的条件可以描述为：
X[A]<>X[B]ANDABS（A-B）<>ABS（X[A]-X[B]）{A和B分别表示两个皇后的行号}
扩展一点DFS——路径搜索：
路径搜索是一个大问题，涉及很多的算法，也关系到生活生产中各个领域。
基础算法即回溯，“高深”一点的算法有最短路Dijkstra算法、欧拉（回）路算法、哈密顿（回）路问题、网络流、启发式搜索等。
回溯算法也有迭代加宽搜索（BFID）、迭代加深搜索（DFID）、A*算法、IDA*、分步搜索等。
在深度优先搜索的过程当中，往往有很多走不通的“死路”。
假如我们把这些“死路”排除在外，不是可以节省很多的时间吗？
打一个比方，前面有一个路径，别人已经提示：
“这是死路，肯定不通”，而你的程序仍然很“执着”地要继续朝这个方向走，走到头来才发现，别人的提示是正确的。
这样，浪费了很多的时间。
针对这种情况，我们可以把“死路”给标记一下不走，就可以得到更高的搜索效率，处理“死路”的这种方法就是启发式搜索、记忆化搜索。
对于一些有最优子结构的问题，我们往往采用动态规划算法来实现。
采用动态规划算法，需要弄清状态以及状态是如何转移的，接着列出状态转移方程。
首先举一个非常简单的例子
例题4数字三角形（经典问题）
分析无论对与新手还是老手，这都是再熟悉不过的题了，很容易地，我们写出状态转移方程：
f（i,j）=a[i,j]+min{f（i+1,j）+f（i,j+1）}
对于动态规划算法解决这个问题，我们根据状态转移方程和状态转移方向，比较容易地写出动态规划的循环表示方法。
但是，当状态和转移非常复杂的时候，也许写出循环式的动态规划就不是那么简单了。
我们尝试从正面的思路去分析问题，如上例，不难得出一个非常简单的递归过程：
if（i==0）return（a[i,j]）;
f1=f（i+1,j）;f2=f（i,j+1）;
iff1>f2returna[i,j]+f1;elsereturna[i,j]+f2;
显而易见，这个算法就是最简单的搜索算法。
时间复杂度为2n，明显是会超时的。
分析一下搜索的过程，实际上，很多调用都是不必要的，也就是把产生过的最优状态，又产生了一次。
为了避免浪费，很显然，我们存放一个opt数组：
Opt[i,j]-每产生一个f（i,j），将f（i,j）的值放入opt中，以后再次调用到f（
升级会员 