【BZOJ 2431】【HAOI 2009】逆序对数列【DP+优化】

3/8/2017来源:ASP.NET技巧人气:1104

Description

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

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

题解

f[i][j]表示到第i个数有j个逆序对,∴f[i][j]=sigma{f[i-1][j-k]) k∈[0,i) 但是这是O(n^3)的,所以我们观察式子,发现好像与前缀和有关,所以可以用前缀和优化一维,变成O(n^2)就可以了。 同时,通过i与i-1可以看出,我们还能使用滚动数组。

代码

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define mod 10000 int f[1010],sum[1010]; int n,k; int main() { scanf("%d%d",&n,&k); for(int i = 0;i <= k;i++) sum[i] = 1; for(int i = 2;i <= n;i++) { f[0] = 1; for(int j = 1;j <= k;j++) if(j-i >= 0) { f[j] = (sum[j] - sum[j-i] + mod) % mod; } else f[j] = sum[j] % mod; for(int j = 1;j <= k;j++) sum[j] = (f[j] + sum[j-1]) % mod; } PRintf("%d\n",f[k]); return 0; }