P2513 [HAOI2009]逆序对数列

2018-06-17 22:02:18来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

题目描述

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

输入输出格式

输入格式:

 

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

 

输出格式:

 

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

 

输入输出样例

输入样例#1:
4 1
输出样例#1:
3

说明

样例说明:

下列3个数列逆序对数都为1;分别是1 2 4 3 ;1 3 2 4 ;2 1 3 4;

测试数据范围

30%的数据 n<=12

100%的数据 n<=1000,k<=1000

 

 

比较不常见的计数问题。

(i=4,k=3为例):

1后面(2,3,4)k=3的方案数

加 2 后面(1,3,4)k=2的方案数

加 3 后面(1,2,4)k=1的方案数

加 4 后面(1,2,3)k=0的方案数

 

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<iostream>
 4 #define lowbit(x) (x)&(-x)
 5 using namespace std;
 6 const int MAXN=2001;
 7 const int mod=10000;
 8 inline void read(int &n){char c='+';bool flag=0;n=0;    
 9 while(c<'0'||c>'9') c=='-'?flag=1,c=getchar():c=getchar();    
10 while(c>='0'&&c<='9') n=n*10+c-48,c=getchar();flag==1?n=-n:n=n;}
11 int dp[MAXN][MAXN];
12 int main()
13 {
14     int n,k;read(n);read(k);
15     dp[1][0]=1;
16     dp[2][0]=1;
17     dp[2][1]=1;
18     dp[3][1]=2;
19     dp[3][2]=2;
20     dp[3][3]=1;
21     dp[3][0]=1;// 特判一下
22     for(int i=4;i<=n;i++)
23     {
24         dp[i][1]=i-1,dp[i][0]=1;
25         for(int j=2;j<=k;j++)
26             for(int l=1;l<=i&&l<=j+1;l++)
27                 dp[i][j]=(dp[i][j]+dp[i-1][j-l+1])%mod;
28      } 
29     printf("%d",dp[n][k]%mod);
30     return 0;
31 }

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:HDU 1575 Tr A(矩阵快速幂)

下一篇:在QT5中实现求两个输入值的和并输出