#火车进站# | 动态规划
火车进站
https://www.nowcoder.com/practice/97ba57c35e9f4749826dc3befaeae109?tpId=37&tags=&title=&difficulty=0&judgeStatus=0&rp=1&sourceUrl=%2Fexam%2Foj%2Fta%3FtpId%3D37
n = int(input())
trainnum = input().split()
def is_legal(trainlist,x,s):
if s>= len(trainlist)-1:
return True
else:
for i in range(len(trainlist)-s-1):
if trainlist[i+s]< trainlist[i+s+1]:
return False
return True
dp = [ [] for _ in range(n+1) ]
dp[1].append([1])
for i in range(2,n+1):
for s in dp[i-1]:
for j in reversed(range(i)):
if is_legal(s,i,j):
dp[i].append(s[:j]+[i]+s[j:])
ans = []
for s in dp[n]:
ans.append([trainnum[item-1] for item in s])
ans.sort()
for s in ans:
print(' '.join(s))
假设进站顺序是1234567，求出所有的解，再把真实进站顺序带入再排序即可（这里我自己也没太搞懂为什么可以这样）。
先从车少的情况开始求，每多加一辆车，因为他编号最大，所以它出站之后后面的出站顺序只能按车号降序。
对所有n-1的合法出站顺序尝试在各个位置添加新车看看是否仍然合法，合法就加到n的合法出站顺序里。
