bzoj2431逆序对数列

时间：2025-01-16 20:36:08

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=2431

很容易想到n^3的做法。就是前 i 个数用第 i 个数最多能 i - 1 个逆序对，所以 i - 1 个数中属于 j ~ j - i + 1 的值都能加到前 i 个数的状态上。

#include<iostream>

#include<cstdio>

#include<cstring>

const int N=,mod=;

int n,k,dp[N][N],sm[N];

int main()

{

    scanf("%d%d",&n,&k);

    for(int i=;i<=n;i++)sm[i]=sm[i-]+i-;

    dp[][]=;

    for(int i=;i<=n;i++)

        for(int j=;j<=k&&j<=sm[i];j++)

            for(int l=j;l>=&&l>=j-i+;l--)

                (dp[i][j]+=dp[i-][l])%=mod;

    printf("%d",dp[n][k]);

    return ;

}

对于 i - 1 用了一个前缀和一样的部分。可以优化掉这个循环。只需要在过程中维护一下sum。很像之前做过的某道题。

不过sum还能变成负数？这样也能算出正确答案？感觉有些奇怪。

#include<iostream>

#include<cstdio>

#include<cstring>

const int N=,mod=;

int n,k,dp[N][N],sm[N],s[N];

int main()

{

    scanf("%d%d",&n,&k);

    dp[][]=;

    for(int i=;i<=n;i++)

    {

        int sum=;

        for(int j=;j<=k;j++)

        {

            (sum+=dp[i-][j])%=mod;

            if(j>=i)sum=((sum-dp[i-][j-i])%mod+mod)%mod;

            dp[i][j]=sum;

        }

    }

    printf("%d",dp[n][k]);

    return ;

}

相关文章