我会告诉你这是三倍经验题吗。。。

做完这道你可以去做P1521 求逆序对和[P2513 [HAOI2009]逆序对数列](https://www.luogu.org/problemnew/show/P2513)

但是我并不确定我的代码在P2513不会TLE

题面

在这道题中，你会发现你逆序对的个数只和相对大小有关！！

然后就可以建立DP模型：$dp[i][j]$表示$i$个不同的数的所有排列中，逆序对数量为$j$的排列个数。初始边界为$dp[1][0]=1$。

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

Code：

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,k,w;
int dp[1001][1001];
int main(){
    scanf("%d",&w);
    while (w--){
        memset(dp,0,sizeof (dp));
        scanf("%d%d",&n,&k);
        dp[1][0]=1;
        for(int i=1;i<=n;i++){
            for(int j=0;j<=k;j++){
                for(int l=0;l<i;l++){
                    if(j>=l)
                        dp[i][j]+=dp[i-1][j-l];
                }
            }
        }
        printf("%d\n",dp[n][k]);
    }
    return 0;
}

本文作者：Snowflake_Pink
本文链接：https://snowflake.pink/archives/3/
最后修改时间：2020-04-13 11:07:18
本站未注明转载的文章均为原创，并采用 CC BY-NC-SA 4.0 授权协议，转载请注明来源，谢谢！