题解|[HAOI2009]逆序对数列

[HAOI2009]逆序对数列

http://www.nowcoder.com/questionTerminal/7012581e4cbf41b69fdedebb2f8837cd

这一题的题面,告诉我们是要求逆序对数为k的数列。

但是, 恐怖的数据范围说明了一切

n<=1000 k<=1000

这么大的数据,对于求逆序对的任何方法都是会TLE的


既然按照题面的说法不行,我们就在我们的知识范围内搜索:

图论?数论?dp?

(实际上并不是这么简单,要多做题才能理解这其中的套路)

没错!就是dp!

在dp中,有一种类型是专门用来计算符合每种规则的dp——计数dp

接下来,就是


设置状态


按照一贯的套路,求什么设什么

我们设f[i][j]为在长度为i的所有排列(全排列)中,逆序对数为j的个数

那么,如果我们想往一个长度为i的数列中加入一个数,使之成为长度为i+1的数列时,会多产生是多少呢?

我们设k表示这次更新会导致增加多少逆序对数

那么dp方程就是

f[i][j]=sigma(f[i-1][j-k])(k=0...min(i-1,j))

这个方程的复杂度很显然是通过不了题目的,所以我们还要进一步优化


我们发现,k是从0一直到一个固定的值的,所以我们可以考虑用前缀和来优化

#include<cstdio>
const long long mod=10000;
long long n,k,sum,f[1010][1010];
int main()
{
    scanf("%lld %lld",&n,&k);
    f[1][0]=1;
    for(long long i=2;i<=n;i++)
    {
        sum=0; //前缀和优化
        for(long long j=0;j<=k;j++)
        {
            sum+=f[i-1][j];
            sum=(sum%mod+mod)%mod; 
            f[i][j]=sum;
            if(j>=i-1)
                sum-=f[i-1][j-i+1],sum=(sum%mod+mod)%mod; }//这里注意要加上模数,不然会产生负数
    }
    printf("%lld\n",f[n][k]);
}




全部评论
感觉有个小小的bug,在第二层循环内,如果k>i就没有意义了?
点赞 回复 分享
发布于 2021-10-10 23:48

相关推荐

07-07 14:30
复旦大学 Java
遇到这种人我也不知道说啥了
正义执行官:人家能回你就不错了,自己不主动去问,等着天上掉馅饼,想啥呢哥们
点赞 评论 收藏
分享
码农索隆:单休一个月少休息4天,一年就是48天,平时节假日,别人3天假期,单休的两天
点赞 评论 收藏
分享
05-26 22:25
门头沟学院 Java
Java小肖:不会是想叫你过去把你打一顿吧,哈哈哈
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-02 17:28
25届每天都在焦虑找工作的事情0offer情绪一直很低落硬撑着面了一个岗位岗位有应酬的成分面试的时候hr给我出各种场景题问的问题比较犀利&nbsp;有点压力面的感觉感觉有点回答不上来本来就压抑的情绪瞬间爆发了呢一瞬间特别想哭觉得自己特别没用没绷住掉眼泪了事后想想觉得自己挺有病的&nbsp;真的破大防了
喜欢唱跳rap小刺猬...:我觉得没关系吧,之前有一次面试leader给我压力面,我顶住了压力,结果入职的时候发现组里氛围很差,果断跑路。其实从面试就能大概看出组的情况,面试体验好的组倒是不一定好,但是面试体验不好的组。。。就很难说
面试尴尬现场
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务