BZOJ2431 HAOI2009 逆序对数列 【DP】*

时间:2021-08-12 00:36:46

BZOJ2431 HAOI2009 逆序对数列


Description

对于一个数列ai{a_i}ai​,如果有i<j且ai&gt;aja_i&gt;a_jai​>aj​,那么我们称aia_iai​与aja_jaj​为一对逆序对数。若对于任意一个由1~n自然数组成的数列,可以很容易求出有多少个逆序对数。那么逆序对数为k的这样自然数数列到底有多少个?

Input

第一行为两个整数n,k。

Output

写入一个整数,表示符合条件的数列个数,由于这个数可能很大,你只需输出该数对10000求余数后的结果。

Sample Input

4 1

Sample Output

3
样例说明:
下列3个数列逆序对数都为1;分别是1 2 4 3 ;1 3 2 4 ;2 1 3 4;
100%的数据 n<=1000,k<=1000


直接考虑DP
dpi,jdp_{i,j}dpi,j​表示i个数存在j个逆序对的方案数
考虑把第i个数放进排列,放在位置j会有i-j个逆序对产生
dpi,j=∑dp{i−1,k}​
然后可以用前缀和优化


 #include<bits/stdc++.h>
using namespace std;
#define fu(a,b,c) for(int a=b;a<=c;++a)
#define fd(a,b,c) for(int a=b;a>=c;--a)
#define LL long long
#define Mod 10000
#define N 1010
int dp[N][N];
int n,k;
int add(int a,int b){return (a+b)%Mod;}
int sub(int a,int b){return (a-b+Mod)%Mod;}
int main(){
scanf("%d%d",&n,&k);
fu(i,,n)dp[i][]=;
fu(i,,n){
fu(j,,k)dp[i-][j]=add(dp[i-][j],dp[i-][j-]);
fu(j,,k){
dp[i][j]=dp[i-][j];
if(j>=i)dp[i][j]=sub(dp[i][j],dp[i-][j-i]);
}
}
printf("%d",dp[n][k]);
return ;
}

BZOJ2431 HAOI2009 逆序对数列 【DP】*的更多相关文章

  1. BZOJ2431&colon;&lbrack;HAOI2009&rsqb;逆序对数列&lpar;DP&comma;差分&rpar;

    Description 对于一个数列{ai},如果有i<j且ai>aj,那么我们称ai与aj为一对逆序对数.若对于任意一个由1~n自然数组成的 数列,可以很容易求出有多少个逆序对数.那么逆 ...

  2. &lbrack;bzoj2431&rsqb;&lbrack;HAOI2009&rsqb;&lbrack;逆序对数列&rsqb; &lpar;dp计数&rpar;

    Description 对于一个数列{ai},如果有i<j且ai>aj,那么我们称ai与aj为一对逆序对数.若对于任意一个由1~n自然数组成的 数列,可以很容易求出有多少个逆序对数.那么逆 ...

  3. &lbrack;BZOJ2431&rsqb;&lbrack;HAOI2009&rsqb;逆序对数列&lpar;DP&rpar;

    从小到大加数,根据加入的位置转移,裸的背包DP. #include<cstdio> #include<cstring> #include<algorithm> #d ...

  4. bzoj2431&colon; &lbrack;HAOI2009&rsqb;逆序对数列&lpar;前缀和优化dp&rpar;

    2431: [HAOI2009]逆序对数列 Time Limit: 5 Sec  Memory Limit: 128 MBSubmit: 2312  Solved: 1330[Submit][Stat ...

  5. BZOJ 2431&colon; &lbrack;HAOI2009&rsqb;逆序对数列&lpar; dp &rpar;

    dp(i,j)表示1~i的全部排列中逆序对数为j的个数. 从1~i-1的全部排列中加入i, 那么可以产生的逆序对数为0~i-1, 所以 dp(i,j) = Σ dp(i-1,k) (j-i+1 ≤ k ...

  6. bzoj千题计划153:bzoj2431&colon; &lbrack;HAOI2009&rsqb;逆序对数列

    http://www.lydsy.com/JudgeOnline/problem.php?id=2431 dp[i][j] 表示i的排列,有j个逆序对的方案数 加入i+1,此时i+1是排列中最大的数, ...

  7. 【bzoj2431】&lbrack;HAOI2009&rsqb;逆序对数列 dp

    题目描述 对于一个数列{ai},如果有i<j且ai>aj,那么我们称ai与aj为一对逆序对数.若对于任意一个由1~n自然数组成的 数列,可以很容易求出有多少个逆序对数.那么逆序对数为k的这 ...

  8. bzoj2431&colon; &lbrack;HAOI2009&rsqb;逆序对数列(DP)

    f[i][j]前i个数有j个逆序对的数量 f[i][j]=sigma(f[i-1][j-k]){1<=k<=i} 维护一个前缀和即可 #include<iostream> #i ...

  9. bzoj2431&colon; &lbrack;HAOI2009&rsqb;逆序对数列

    dp. f[i][j]表示放置第i个数有j个逆序对的方案数. s[i][j]维护前缀和(f[i][0]~f[i][j]). 状态转移方程 f[i][j]=s[i-1][j]-s[i-1][max(j- ...

随机推荐

  1. 解决:&sol;bin&sol;sh&colon; 1&colon; &sol;home&sol;&ast;&ast;&sol;custom&lowbar;app&period;sh&colon; Permission denied错误

    出现如下错误,一般是执行权限不够. /bin/sh: : /home/custom_app.sh: Permission denied 解决方法是:cd 到此文件目录,对提示的文件赋予可执行权限或读写 ...

  2. Spring Bean后处理器以及容器后处理器【转】

    Bean后处理器:即当spring容器实例化Bean实例之后进行的增强处理. 容器后处理器:对容器本身进行处理,并总是在容器实例化其他任何Bean之前读取配置文件的元数据并可能修改这些数据. 一.Be ...

  3. C&num;程序设计----&gt&semi;计算圆面积windows程序

    值得说的就是添加一个回车事件, http://blog.csdn.net/nanwang314/article/details/6176604 private void textBox1_KeyDow ...

  4. crond&colon; unrecognized service 无crond解决办法

    运行计划任务时:service crond restart提示:crond: unrecognized service安装计划任务:yum -y install vixie-cron 另外附计划任务的 ...

  5. c&plus;&plus; 继承多个类 及虚函数

    #include <iostream>using namespace std; class BaseA {public:    virtual void say() {        co ...

  6. Android 侧滑菜单的简单实现(SlidingMenu)二

    在上一篇博文中已经简单的实现了侧滑菜单,代码也很简单,就几行代码. 这篇文章依然讲侧滑菜单,与前一篇文章不同的是,这篇文章用不同的代码方式来实现侧滑菜单. 在前面的文章中已经用了在Activity中通 ...

  7. PHP unlink&lpar;&rpar; 函数

    定义和用法 unlink() 函数删除文件. 若成功,则返回 true,失败则返回 false. 语法 unlink(filename,context) 参数 描述 filename 必需.规定要删除 ...

  8. Readprocessmemory使用方法

    函数功能:该函数从指定的进程中读入内存信息,被读取的区域必须具有訪问权限. 函数原型:BOOL ReadProcessMemory(HANDLE hProcess,LPCVOID lpBaseAddr ...

  9. Linux下hosts、host&period;conf、resolv&period;conf

    /etc/resolv.conf 该文件是DNS域名解析的配置文件,它的格式很简单,每行以一个关键字开头,后接配置参数. resolv.conf的关键字主要有四个,分别是: nameserver   ...

  10. 可遇不可求的Question之导入mysql中文乱码解决方法篇

    可遇不可求的Question之导入mysql中文乱码解决方法篇 先 set names utf8;然后 source c:\1.sql ?