bzoj2431逆序对数列——递推
2024-08-29 18:34:14
题目:https://www.lydsy.com/JudgeOnline/problem.php?id=2431
考虑新加入一个数i,根据放的位置不同,可以产生0~i-1个新逆序对;
所以f[i][j]可由f[i-1][j-k]相加得到,其中0<=k<=i-1&&k<=j;
再优化一下,每次前缀和减掉最前一个,加上最后一个,保持在合法范围内更新即可。
代码如下:
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m,sum;
int f[][],p=; int main(){
scanf("%d%d",&n,&m);
f[][]=;
/*
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
for(int k=0;k<i&&k<=j;k++)
(f[i][j]+=f[i-1][j-k])%=p;
*/
for (int i=;i<=n;i++){
sum=;
for (int j=;j<=m;j++){
if (j>=i)sum=(sum-f[i-][j-i]+p)%p;
(sum+=f[i-][j])%=p;
f[i][j]=sum;
}
}
printf("%d",f[n][m]);
return ;
}
最新文章
- Patching Array
- 领域模型驱动设计(Domain Driven Design)入门概述
- js-设置焦点
- linux kernel 字符设备详解
- JAVA学习Swing章节流布局管理器简单学习
- 学习OpenCV——配置CUDA环境
- des算法的C#实现
- [转] LCA与Tarjan
- 常用google产品
- (转)HTML特殊字符
- eq,neq,gt,lt等表达式缩写
- J2EE应用服务器计数器
- Oracle ADDM报告生成和性能分析
- Struts2——通配符,Action Method_DMI
- DNA甲基化测序方法介绍
- postfix 如何设置邮件头翻译的功能
- redis 单节点安装
- Thread.currentThread()与this的区别
- 递归神经网络(Recursive Neural Network, RNN)
- C# 动态获取代码所在行号
热门文章
- 深究Spring中Bean的生命周期
- http://www.cnblogs.com/shihaiming/
- TeX系列: tikz-3dplot绘图宏包
- 常见的哈希Hash算法 &; MD5 &; 对称非对称加密 &; 海明码
- Spring boot 整合spring Data JPA+Spring Security+Thymeleaf框架(上)
- TFTP服务器
- [CSS3] Understand CSS Selector Specificity
- lua 暂停写法
- indexOf 和 lastIndexOf 的区别
- fetch 函数分装