您所在位置：主题：[讨论]双栈出列问题
Benix
[专家分：720] 发布于 2006-04-04 13:42:00
题目应该很大众化了 有N个车厢 排成一列(1,2,3...N) 经过两个栈 问有多少种出栈的可能 我想出一种DP的方法 但不知道对不对
设 m[i]为i各车厢出单栈的可能数 s为N个车厢出双栈的可能数 那么
for j:=0 to N-1 do
s:=m[j]*j!+m[N-j-1]*(N-j-1)!
其中有三个问题
1.这种算法是否正确？
2.i个车厢出单栈的可能数如何用DP来算
3.数据规模太大 能否有那位高人提供一下200以内的测试数据
谢
设 m[i]为i各车厢出单栈的可能数 s为N个车厢出双栈的可能数 那么
for j:=0 to N-1 do
s:=m[j]*j!+m[N-j-1]*(N-j-1)!
其中有三个问题
1.这种算法是否正确？
2.i个车厢出单栈的可能数如何用DP来算
3.数据规模太大 能否有那位高人提供一下200以内的测试数据
谢