自动搬运

查看原文

来自洛谷，原作者为

	小周猪猪 稳定AFO的老年退役女选手

搬运于2025-08-24 21:26:01，当前版本为作者最后更新于2018-07-23 17:34:10，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

貌似这道题不需要求前缀和,滚动数组之类的优化吧...

其实这是一道递推（说的高级一点就是DP）

我们就设f[i][j]为前i个数字(即1-i)构成逆序对数为j的方案总数

这么怎么转移么......emmmm.....我们可以尝试着用递推的思路去推一下

假设当前枚举是这个二维数组的下标分别是i和j，又有那么可以知道，插入的数字是i，以及计算完了前i个数字的逆序对方案书，用(形象)的方式去表示，就是: ########（超形象的吧）

当插入的这个数字在这个这串数字的末尾时：就是：########i,此时这串数列的逆序对方案数就是前i-1的方案数，因为在末尾，和任何一个数都不构成逆序对，即f[i-1][j]

同理：当插入的位置为######i#时，i和后面的一个数字构成了一个逆序对，那么必然是f[i-1][j-1],即逆序对的个个数需要减去1，数字的个数不变.

同理，接下来便是：f[i-1][j-2],f[i-1][j-3],f[i-1][j-4]......

直到：i########,循环到第i-1次的时候，方案数是f[i-1][j-i-1]

因此，我们可以得到：

至于sum是什么玩意儿，也就是求和的嘛...

代码如下：

#include<bits/stdc++.h>
using namespace std;
int N,K;
int f[5000][5000];
int main()
{
	cin>>N>>K;
	f[1][0]=1;
	f[2][1]=1;
	f[2][0]=1;
	f[0][0]=1;
	for (int i=3;i<=N;i++)
		for (int j=0;j<=K;j++)
		    for (int k=0;k<=i-1&&j-k>=0;k++)
				f[i][j]=(f[i-1][j-k]+f[i][j])%10000;//记得取模
	cout<<f[N][K]<<endl;
	return 0; 
}