Loading...

洛谷P2513 [HAOI2009]逆序对数列

check评论:0 条 remove_red_eye浏览量:214 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2019-10-27

原题链接

  • 题目描述
给定n,k,求有多少种n的排列有k个逆序对
  • 题目分析

令$dp[i][j]$表示有多少种$i$的排列中恰好有$j$对逆序对

显然我们加进去一个最大的数$i$,最多产生$i-1$对逆序对

可以得到转移方程$dp[i][j]=\sum\limits_{max(j-i+1,0)}^j dp[i-1][j]$

这个可以前缀和优化,总时间复杂度$O(nk)$

  • 代码实现
/*deco loves Chino*/
#include <bits/stdc++.h>
using namespace std;
int dp[1010][1010];
int n,k;
int main()
{
    cin>>n>>k;
    dp[1][0]=1;
    for(int i=1;i<=k;i++)
    {
        dp[1][i]=1;
    }
    for(int i=1;i<=n;i++)
    {
        dp[i][0]=1;
    }
    for(int i=2;i<=n;i++)
    {
        for(int j=1;j<=k;j++)
        {
            int qaq=j-i+1;
            qaq=max(qaq,0);
            int pwp=0;
            if(qaq!=0)
            {
                pwp=dp[i-1][qaq-1];
            }
            dp[i][j]=dp[i-1][j]-pwp;
            dp[i][j]+=dp[i][j-1];
        }
    }
    cout<<dp[n][k]-dp[n][k-1];
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名