BZOJ2431 [HAOI2009]逆序对数列 【dp】

题目

对于一个数列{ai}，如果有i

输入格式

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

输出格式

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

输入样例

4 1

输出样例

3

提示

样例说明：

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

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

题解

设$f[i][j]$表示前i个数组成j个逆序对的数列的方案数
$f[i][j]=\sum_{k=0}^{i-1}f[i-1][j-k]$
解释：插入第i个数，可能多产生0至i - 1个逆序对
求个前缀和优化一下

#include<cstdio>
#define min(a,b) ((a) < (b) ? (a) : (b))
const int maxn = 1005,maxm = 100005,INF = 1000000000,P = 10000;
int f[maxn][maxn],s[maxn][maxn],N,K;
int main(){
 scanf("%d%d",&N,&K);
 f[1][0] = 1;
 for (int i = 0; i <= K; i++) s[1][i] = 1;
 for (int i = 2; i <= N; i++){
    
 for (int j = 0; j <= K; j++){
    
 f[i][j] = s[i - 1][j];
 if (j - i >= 0) f[i][j] -= s[i - 1][j - i];
 f[i][j] = (f[i][j] + P) % P;
 }
 s[i][0] = 1;
 for (int j = 1; j <= K; j++) s[i][j] = (s[i][j - 1] + f[i][j]) % P;
 }
 printf("%d",f[N][K]);
 return 0;
}