dp(i,j)表示1~i的全部排列中逆序对数为j的个数.
从1~i-1的全部排列中加入i, 那么可以产生的逆序对数为0~i-1, 所以 dp(i,j) = Σ dp(i-1,k) (j-i+1 ≤ k ≤ j) 用前缀和优化就可以做到O(N2)了
---------------------------------------------------------------------
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1009;
const int MOD = 10000;
int N, K, dp[maxn][maxn], cnt[maxn];
int main() {
scanf("%d%d", &N, &K);
memset(dp, 0, sizeof dp);
dp[0][1] = 1;
for(int i = 0; i <= K; i++) cnt[i] = 1;
for(int i = 1; i <= N; i++) {
for(int j = 0; j <= K; j++) {
dp[i][j] = cnt[j];
if(j - i >= 0)
dp[i][j] -= cnt[j - i];
if(dp[i][j] < 0)
dp[i][j] += MOD;
else if(dp[i][j] >= MOD)
dp[i][j] -= MOD;
}
cnt[0] = dp[i][0];
for(int j = 1; j <= K; j++) {
cnt[j] = cnt[j - 1] + dp[i][j];
if(cnt[j] >= MOD)
cnt[j] -= MOD;
}
}
printf("%d\n", dp[N][K]);
return 0;
}
---------------------------------------------------------------------
2431: [HAOI2009]逆序对数列
Time Limit: 5 Sec Memory Limit: 128 MB
Submit: 1228 Solved: 712
[Submit][Status][Discuss]Description
对于一个数列{ai}，如果有i<j且ai>aj，那么我们称ai与aj为一对逆序对数。若对于任意一个由1~n自然数组成的数列，可以很容易求出有多少个逆序对数。那么逆序对数为k的这样自然数数列到底有多少个？
Input
Output
写入一个整数，表示符合条件的数列个数，由于这个数可能很大，你只需输出该数对10000求余数后的结果。
Sample Input
样例输入
4 1
Sample Output
样例输出
3
样例说明：
下列3个数列逆序对数都为1；分别是1 2 4 3 ；1 3 2 4 ；2 1 3 4；
测试数据范围
30%的数据 n<=12
100%的数据 n<=1000，k<=1000
HINT
Source
BZOJ 2431: [HAOI2009]逆序对数列( dp )
原文：http://www.cnblogs.com/JSZX11556/p/4840808.html
