动态规划、前缀和

动态规划,设计 $dp_{i,j}$ 为长度为 $i$ 且逆序对数为 $j$ 的排列数量。考虑向长度为 $i-1$ 的排列中插入数字 $i$ 使其长度增加,根据插入位置不同可以让序列的逆序对数量增加 $0 \sim i-1$ 个。边界条件 $dp_{1,0}=1$。

$$dp_{i,j}=\sum\limits_{k=0}^{\min(i-1,j)} dp_{i-1,j-k}$$

时间复杂度 $O(n^2m)$,考虑优化。容易发现转移是一个前缀和的形式,维护 $dp_{i-1}$ 的前缀和即可 $O(1)$ 转移。

最终时间复杂度 $O(nm)$。

#include<bits/stdc++.h>
using namespace std;
constexpr int mod=1'000'000'007;
int n,m,sum[10'005],dp[1'005][10'005];
int main(){
    scanf("%d%d",&n,&m);
    sum[0]=1,dp[1][0]=1;
    for(int i=2;i<=n;i++){
        for(int j=1;j<=m;j++) sum[j]=(sum[j-1]+dp[i-1][j])%mod;
        for(int j=0;j<=m;j++)
            if(j-min(i-1,j)==0) dp[i][j]=sum[j];
            else dp[i][j]=(sum[j]-sum[j-min(i-1,j)-1])%mod;
    }
    dp[n][m]=(dp[n][m]+mod)%mod;
    printf("%d\n",dp[n][m]);
    return 0;
}
最后修改:2024 年 08 月 06 日
如果觉得我的文章对你有用,请随意赞赏