蓝桥杯OJ240 排列数

1. MOD=123456
2. n,k=map(int,input().split())#求k-1个折点
3. dp=[[[0]*(k) for i in range(3) ]for j in range(n+1)]
4. dp[1][1][0]=1
5. dp[2][1][0]=2
6. dp[3][2][1]=dp[3][0][1]=2
7. dp[3][1][0]=2
8. for i in range(4,n+1):
9.     for j in range(3):
10.         for t in range(0,min(k,i)):
11.             dp[i][j][t]+=dp[i-1][j][t]*(t+1)
12.             if t>=2:
13.                 dp[i][j][t]+=dp[i-1][j][t-2]*(i-t-1)#注意不是*(i-t-3)
14.             if t>=1:
15.                 if j==0 or j==2:       dp[i][j][t]+=dp[i-1][1][t-1]
16.                 if j==1:               dp[i][1][t]+=2*dp[i-1][2][t-1]+2*dp[i-1][0][t-1]
17.             dp[i][j][t]%=MOD
18. print((dp[n][0][k-1]+dp[n][1][k-1]+dp[n][2][k-1])%MOD)

复制代码

构建一个dp数组，dp[j][k] i代表一共i个数来排列。j代表3个状态。k代表k个折点。(代码中用dp[j][t]表示，并没有什么意思，只是符号不敷用了。。。）
现在来分析三个状态：
j==0 代表wwwww的外形的序列，两端都是较大值
j==1 代表NNNNNNNNNNN的外形的序列，两端分别是较大值和较小值
j==2 代表mmmmmmmmmm的外形的序列，两端都是较小值
 如图所示：

 然后分别讨论dp[j][k]的递推关系

前面的红笔写的是递推时要乘上的系数
然后再整理一下就能得到代码中的递推公式了~

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。