逆序排列 51Nod - 1020

本文主要是介绍逆序排列 51Nod - 1020，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

https://www.51nod.com/Challenge/Problem.html#!#problemId=1020

按组合数考虑半天 看题解是dp。。

考虑对于[1,n-1]的某个全排列 将n插入后 其后面有几个数就产生几个逆序数

 

题解：
设f(n,k)表示n个数的排列中逆序数个数为k的排列数。

最大的数n可能会排在第n-i位，从而产生i个与n有关的逆序对，去掉n之后，剩下的n-1个数的排列有k-i个逆序对。所以，f(n,k)=求和(f(n-1，k-i))(0<=i<n)。

同理有f(n,k-1)=求和(f(n-1，k-1-i))(0<=i<n)。

两式相减，可得f(n,k)-f(n,k-1)=f(n-1,k)-f(n-1,k-n)。

递推公式为f(n,k)=f(n,k-1)+f(n-1,k)-f(n-1,k-n)。

 

 

 

 

 

 

 

 

 

 

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=1e3+10;
const int maxk=2e4+10;int dp[maxn][maxk];void init()
{ll a,b,c;int i,j;dp[1][0]=1;for(i=1;i<=1000;i++) dp[i][0]=1;for(i=1;i<=1000;i++){for(j=1;j<=i*(i-1)/2&&j<=20000;j++){a=dp[i-1][j],b=dp[i][j-1];c=(a+b)%mod;dp[i][j]=c;if(i<=j){a=dp[i][j]-dp[i-1][j-i],b=mod;c=(a+b)%mod;dp[i][j]=c;}}}
}int main()
{int t,n,k;init();scanf("%d",&t);while(t--){scanf("%d%d",&n,&k);printf("%lld\n",dp[n][k]);}return 0;
}

 

这篇关于逆序排列 51Nod - 1020的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---