51Nod1020 逆序排列

动态规划 dp

51Nod

很明显的 DP 有木有

设 $f(i,j)$ 为 $1$ 到 $i$ 的全排列中有多少个逆序对数为 $j$。

那么每次转移的时候只要枚举一下将新数插入到哪里就行（它会与其后面的所有数产生逆序对）。

但是这样子转移的话总复杂度是 $O(n^3)$ 的 直接gg。。。

把 $f(i,j)$ 和 $f(i,j-1)$ 的式子写出来，再相减就可以得到 $f(i-1,j)-f(i-1,j-i) * [j \geq i]$ 。那么就可以 $O(1)$ 转移了。

其实也可以写前缀和优化的。。。

#include <iostream>
#include <cstdio>
#include <cstring>
const int MOD = 1e9 + 7;
const int MAXN = 1000 + 5;
const int MAXK = 20000 + 5;
int T, N, K;
int Dp[MAXN][MAXK];
inline int read()
{
    register int x = 0;
    register char ch = getchar();
    while(!isdigit(ch)) ch = getchar();
    while(isdigit(ch))
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x;
}
int main()
{
    for(int i = 1; i <= 1000; ++i)
    {
        Dp[i][0] = 1;
        for(int j = 1; j <= std::min(20000, i * (i - 1) / 2); ++j)
        {
            Dp[i][j] = (Dp[i][j - 1] + Dp[i - 1][j]) % MOD;
            if(j >= i) (Dp[i][j] -= Dp[i - 1][j - i] - MOD) %= MOD;
        }
    }
    T = read();
    while(T--)
    {
        N = read();
        K = read();
        printf("%d\n", (Dp[N][K] + MOD) % MOD);
    }
    return 0;
}