SP64 [PERMUT1 - Permutations]

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

做完这道你可以去做 P1521 求逆序对P2513 [HAOI2009]逆序对数列

但是我并不确定我的代码在 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;
}

本文链接:https://snowflake.pink/archives/3/
This blog is under a CC BY-NC-ND 4.0 Unported License