题解 P1521 【求逆序对】

· · 题解

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

其实这是一道递推（说的高级一点就是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]

因此，我们可以得到：

f[i][j]=sum(f[i-1][j-k])0≤k≤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; 
}