逆序对数列

· · 题解

双倍经验题！

切掉这题就可以切掉P1521了

首先设立状态：f[i][j] 表示i个数逆序对数量为j的个数

转移方程：f[i][j]=∑(s=0,1,...,i-1) f[i-1][j-s]

解释一下这个方程：当有i-1个数时，有j-1个逆序对时，添加第i个数，必有一个位置刚好使逆序对数+1，即可转移到f[i][j]。同理j-2,j-3……j-(i-1),因为只有i-1个数，所以最多到j-(i-1),当然也可能不增加逆序对，即j-0;

但是这样转移需要O(k)的复杂度，总复杂度为O(nk^2)，这是无法承受的。

下面用到前缀优化：

转移状态是连续的，我们可以记sum[i][j]=f[i][0]+f[i][1]+……+f[i][j];

转移方程就变为：f[i][j]=sum[i-1][j]-(j>i?sum[i-1][j-i]:0)

复杂度降为O(nk)，轻松水过去

代码极短：

#include<bits/stdc++.h>
using namespace std;
int n,k,f[1005][1005],sum[10005]; //f[i][j] 表示i个数逆序对数量为j的个数，sum[i]记录前缀，这里优化了一下空间，减了一维
int main()
{
    scanf("%d%d",&n,&k);
    f[0][0]=1;  //初始状态
    for(int i=0;i<=k;i++) sum[i]=1;  //初始指为1
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=k;j++)
            if(j>=i) f[i][j]=(sum[j]-sum[j-i]+10000)%10000; //状态转移，要加10000再取模，不然可能小于0
            else f[i][j]=sum[j]%10000; 
        sum[0]=f[i][0]%10000;  
        for(int j=1;j<=k;j++)   
            sum[j]=(f[i][j]+sum[j-1])%10000; //更新sum，用于下一轮状态转移
    }
    printf("%d",f[n][k]);
}