当前位置: 代码迷 >> 综合 >> 逆序排列 51Nod - 1020 (dp)
  详细解决方案

逆序排列 51Nod - 1020 (dp)

热度:94   发布时间:2023-12-12 14:19:54.0

逆序排列

在一个排列中,如果一对数的前后位置与大小顺序相反,即前面的数大于后面的数,那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。
如2 4 3 1中,2 1,4 3,4 1,3 1是逆序,逆序数是4。

1-n的全排列中,逆序数最小为0(正序),最大为n*(n-1) / 2(倒序)
给出2个数n和k,求1-n的全排列中,逆序数为k的排列有多少种?
例如:n = 4 k = 3。

1 2 3 4的排列中逆序为3的共有6个,分别是:
1 4 3 2
2 3 4 1
2 4 1 3
3 1 4 2
3 2 1 4
4 1 2 3

由于逆序排列的数量非常大,因此只需计算并输出该数 Mod 10^9 + 7的结果就可以了。

Input
第1行:一个数T,表示后面用作输入测试的数的数量。(1 <= T <= 10000)
第2 - T + 1行:每行2个数n,k。中间用空格分隔。(2 <= n <= 1000, 0 <= k <= 20000)

Output
共T行,对应逆序排列的数量 Mod (10^9 + 7)

Input示例
1
4 3

Output示例
6

题意分析:
这道题,如果没有想到动态规划的话,很难想到其他的方法,动态规划的一个思想应该就是,下一个状态和上一个状态之间又怎样的联系,如果你找到了这个联系,然后通过分析整理,得到一个动态转移方程,那么你离AC这道题就不远了。这道题可以作为动态规划的一个典型例题,应为动态转移方程的推导过程很不错,话不多说,让我们来看看如何推导的吧!

推导过程:
首先,你要想到一个动态转移dp【i】【j】数组,并且确定好代表什么意思,
dp【i】【j】表示:1到i这i个数字的全排列当中,逆序数为j的排列数,
这个数组的含义对后面的过程意思我觉得挺大的,要不都无从下手,
下面开始分析:上下两个状态之间的联系
dp【n】【k】=Σdp【n-1】【k-i】(0<=i<=n-1)
在0到n-1数字当中再加入一个数字n,该数字n有n-1个n个位置可以放,放这n个位置的时候还会额外的增加排列的逆序数,当放在首位置(i = 0),由于后面的都比数字n小,不会增加逆序数,当放在后面的位置时( 0 < i <= n-1),会相应的增加逆序数(因为,新加入的数字n比原来的其他数字都要大),好好想一想,可以想通的,画一画。
然后先按就是数学方面的公式推导过程了,数学不太好的朋友要看仔细了:
①dp【n】【k】=Σdp【n-1】【k-i】(0<=i<=n-1)
②dp【n】【k-1】=Σdp【n-1】【k-1-i】(0<=i<=n-1),(有上个等式得到)
③用①减去②得到:dp【n】【k】-dp【n】【k-1】=dp【n-1】【k】-dp【n-i】【k-n】;
④那么就有:dp【n】【k】=dp【n】【k-1】+dp【n-1】【k】-dp【n-i】【k-n】;

看到最后一步的整理后的等式,有的朋友可能回想,唉,博主这个最后这个式子是不是错了呀,其实没有错,
Σdp【n-1】【k-i】 - Σdp【n-1】【k-1-i】,当先把这两个求个公式全部写出来的时候,因为式子是随着 i 的增大而减小的,所以有的朋友可能是想列举出第一个和最后一个,然后在补充一下中间的几个,有可能会写错,我们可以从 i 减小的方式来写,就不会写错了,就会的出上面的那个最终结果了。

大家是不是已经的出来最后的正确结果了呀!是不是很开心,是不是很兴奋!是不是停不下来!哈哈
这个题大家已经随着博客的讲解推导出来了,那么大家再结合这道题想一想类似的动态规划题目的,解题思路,好好理解一下!

(看代码之前还有一个问题:既然动态规划思想是由上一个状态来推导下一个状态的,那么最初的状态有何而来,怎么得到呢,想一想这道题,一般来说最初的状态由于牵涉的数据都是很小的,一般都可以之间看出结果!!!)

代码如下:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define LL long long
using namespace std;const int MOD = 1e9 + 7;
int dp[1003][20004];void make_table()
{for (int i = 1; i <= 1000; i++){dp[i][0] = 1;for (int j = 1; j <= i*(i-1)/2 &&j <= 20000; j++){//这里要注意的是推导出来的公式有的公式是由限制范围的int temp1 = 0, temp2 = 0, temp3 = 0;temp1 = dp[i-1][j];temp2 = dp[i][j-1];if (j-i >= 0) temp3 = dp[i-1][j-i];dp[i][j] = ((temp1 - temp3 + temp2)%MOD + MOD) % MOD;}}
}int main()
{int t;cin >> t;make_table();while (t--){int n, k;scanf("%d%d", &n, &k);printf("%d\n", dp[n][k]);}return 0;
}