题意：
逆序对指在一个序列中ai>aj && i < j，也就是一前一后两个数，当大的在前面的时候即算一对。

题目求在一个由1…n组成的序列中逆序对为k的序列的个数。
出题人很良心，不需要写高精度，答案对10000取模即可。

思路：
这道题的前面其实还有一道很类似的题，也是求逆序对。不同的是那道题给定了序列求逆序对的个数，而这道题则相反。那道题的方法即merge sort。尽管两题很类似，但是方法却截然不同。

凭感觉，这应该是一道动规的题。长度为n-1的序列与长度为n的序列只差一个n，而由于n出现的逆序对也很好求：n在第i个就会相比于原序列多出n-i个逆序对。如此，那看来是动规无疑了。

状态转移方程：若长度为n的序列要求有k个逆序对，那么他可以从长为n-1的序列中选取有k-n+1到k个逆序对的部分。道理很简单n的加入最多使原序列增加n-1个逆序对（即放在第一个的时候，与后面n-1个数构成逆序对），所以要从x[n-I][p]变到x[n][k]，p属于[k-n+1,k]。那么转移方程式就很好写了：

for(unsigned i = 2; i != n+1; ++i)

{

    dp[i][0] = 1;

    for(unsigned j = 1; j != k+1; ++j)

    {

        for(unsigned p = k-j+1; p != j+1; ++p)

        {

            dp[i][j] += dp[i-1][p];

        }

    }

}

优化：
这是一个O(n^3)的算法，很慢。我们观察最内层循环，发现它很多余，因为总是重复操作。dp[i][j-1]和dp[i][j]当i-j+1>0的时候，中间部分完全相同，只是掐头增尾的问题。由此我们可以有第一种优化：dp[i][j] = dp[i][j-1]-dp[i-1][j-i]+dp[i-1][j];（j-i >-1）

当然也可以直接采用前缀数组和的方式将这段循环优化掉，到O(n^2)。
（后面的代码采取的是这一种）

源代码的读入是多组数据。

---

源代码：

#include <bits/stdc++.h>

#define maxn 1005

#define mod 10000

//#define DEBUG

#ifdef DEBUG

#define debug(...)printf(__VA_ARGS__);

#else

#define debug(...)

#endif

using namespace std;

int n[15], k[15], dp[maxn][maxn*10];

void Dp(int n, int k)

{

    int a;

    memset(dp, 0, sizeof dp);

    for(unsigned i = 0; i != k+1; ++i)

    {

        dp[1][i] = 1;

    }

    for(int i = 2; i != n+1; ++i)

    {

        dp[i][0] = 1;

        for(int j = 1; j != k+1; ++j)

        {

            if(j-i > -1)    a = dp[i-1][j-i];

            else a = 0;

            dp[i][j] = (dp[i][j-1]+dp[i-1][j]-a+mod)%mod;

            debug("%d ", dp[i][j]);

        }

        debug("\n");

    }

    return ;

}

int main()

{

    //freopen("test.in", "r", stdin);

    int times, Maxn = 0, Maxk = 0;

    scanf("%d", &times);

    for(unsigned i = 0; i != times; ++i)

    {

        scanf("%d%d", &n[i], &k[i]);

        Maxn = max(Maxn, n[i]);

        Maxk = max(Maxk, k[i]);

    }

    Dp(Maxn, Maxk);

    for(unsigned i = 0; i != times; ++i)

    {

        printf("%d\n", (mod+dp[n[i][k[i]]-dp[n[i]][k[i]-1])%mod);

    }

    return 0;

}

箜瑟_qi 2017.04.27 15:01