考虑一下插⼊法$n<=100$$f[i][j]$表⽰$1$~$i$的全排列有j个逆序对的⽅案数$f[i][j]=\Sigma f[i-1][j-k](0<=k<=i-1)$O(m∗n2)O(m*n^2)O(m∗n2)

拓展：如果$n<=1000$呢？

$n<=1000$?$f[i][j]$是$f[i-1]$中连续⼀段的和 前缀和优化$O(n\ast m)$

下面上非拓展的代码：

#include<cstdio> using namespace std; int f[105][6005]; int main() { int n,k; scanf("%d%d",&n,&k); f[1][0]=1; f[2][0]=1; f[2][1]=1; f[0][0]=1; for(int i=3;i<=n;i++) { for(int j=0;j<=k;j++) { for(int kk=0;kk<=i-1&&kk<=j;kk++) { f[i][j]+=f[i-1][j-kk]000; } } } printf("%d",f[n][k]000); return 0; }

转载于:https://www.cnblogs.com/vercont/p/10210092.html

相关资源：JAVA上百实例源码以及开源项目