orz想了好久好久的排列组合，未果，考虑不全……DP好难啊233333
抛开整体不考虑，我们来考虑一下第i位（k）的插入问题：
第i位>第i-1位时，插入条件为第i-1位<第i-2位
第i位<第i-1位时，插入条件为第i-1位>第i-2位
设f[i][j]为排列的第i位为j，而且i-1位比j矮
设g[i][j]为排列的第i位位j，而且i-1位比j高
ans[i]为i个人的排列情况
那么，f[i][j]=∑f[i-1][k] (k为1~j-1,即第i-1位为小于j的k,f[i-1][k]求和)
g[i][j]=∑g[i-1][k] (同理，k为j+1~n,即第i-1位为大于j的k，g[i-1][k]求和)
从上面的假设可以得到，ans[i]=∑f[i-1][p]+∑g[i-1][q]
其中，p∈[i+1,n],q∈[1,i-1]
然后……有一个很神奇的现象？
1324, 2143, 3142, 2314, 3412, 4231, 4132, 2413, 3241, 1423
比如样例，可以发现，f[4][1]=f[4][4],f[4][2]=f[4][3],
f[4][1]=g[4][4],f[4][2]=g[4][3],f[4][3]=g[4][2],f[4][4]=g[4][1]
f[i][j]=f[i][i-j+1]
g[i][j]=f[i][i-j+1]
也就是说，f[i][j]和g[i][j]是相等的，感觉，，，毕竟排列情况关于中间位置是对称的
ans[i]=2*∑f[i-1][j] 其中，j∈[1,i-1]
/* f[i][j]=f[i-1][j-1]+f[i-1][j-2]+...+f[i-1][1]
=f[i-1][i-j+1]+f[i-1][i-j+2]+...+f[i-1][i-1]
f[i][j-1]=f[i-1]][i-j+2]+...+f[i-1][i-1]*/
所以，f[i][j]=f[i-1][i-j+1]+f[i][j-1] -----这里对应的是开始的两个为递增的情况
另外g[i][j]同理，又可知g[i][j]=f[i][j]，ans[i]=2*∑f[i][j] (j为[1,i])
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int MAX= 13e5; int t,n,m; ll dp[25][25]; ll ans[25]; void init() { memset(ans,0,sizeof(ans)); dp[1][1]=1; ans[1]=1; for(int i=2;i<25;i++) for(int j=2;j<=i;j++) { dp[i][j]=dp[i-1][i-j+1]+dp[i][j-1]; ans[i]+=dp[i][j]*2; } } int main() { cin>>t; init(); while(t--) { cin>>n>>m; cout<<n<<" "<<ans[m]<<endl; } return 0; }