SP64 [PERMUT1 - Permutations]
浏览 1370 | 评论 0 | 字数 1030
Snowflake_Pink
2018年12月08日
  • 我会告诉你这是三倍经验题吗。。。

    做完这道你可以去做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 授权协议,转载请注明来源,谢谢!
    评论
    评论会由可爱的 AI 来审核鸭~
    textsms
    支持 Markdown 语法
    email
    link
    评论列表
    暂无评论