给定一个初始为空的栈，和n个操作组成的操作序列，每个操作只可能是出栈或者入栈。
要求在操作序列的执行过程中不会出现非法的操作，即不会在空栈时执行出栈操作，同时保证当操作序列完成后，栈恰好为一个空栈。
求符合条件的操作序列种类。
例如，4个操作组成的操作序列符合条件的如下：
入栈，出栈，入栈，出栈
入栈，入栈，出栈，出栈
共2种。
1245: 出入栈
时间限制: 1 Sec 内存限制: 128 MB提交: 2 解决: 2
[提交][状态][讨论版][命题人:]
题目描述
输入描述
输入包含多组测试用例，每组测试用例仅包含一个整数n(1<=n<=1000)。
输出描述
输出仅一个整数，表示符合条件的序列总数，为了防止总数过多超出int的范围，结果对1000000007取模(mod 1000000007)。
样例输入
2
3
4
5
10样例输出
1
0
2
0
42提示
友情提示：如(x,y)表示共进行x次入栈和y次出栈。那么y必不大于x，要求(x,y)情况下操作序列的种类数。我们只需知道(x,y-1)和(x-1,y)时的种类数。前者在各可能序列最后加上一次出栈操作。后者在各可能序列最后加上一次入栈操作。即得出dp(x,y)=dp(x,y-1)+dp(x-1,y)时的种类数。
来源
-
Anything about this OnlineJudge, Please Contact Administrator. Click add QQ
OJ system based on HUSTOJ Project , UI based on Twitter Bootstrap
Copyright 2016 ACM算法攻关部
关于网站改版