BZOJ2431 [HAOI2009]逆序对数列

2014.12.09 20:49 Tue| 3 visits oi_2015| 2015_刷题日常| Text

Solution

简单DP。$f[i][j]$ 表示前 $i$ 个数组成逆序对数为 $j$ 的方案数。于是 $f[i][j]=\sum\limits _{k=j-i+1} ^j f[i-1][k]$ 。又因为 $f[i][j-1]=\sum \limits _{k=j-i} ^{j-1} f[i-1][k]$ ,所以 $f[i][j]=(f[i][j-1]-f[i-1][j-i]+f[i-1][j]$ 。蒟蒻太懒,不想判断边界,然后就把数组开大一点,让它随便溢出好了……

Code

#include <bits/stdc++.h>
using namespace std;
#define N 1005
#define mod 10000

int n,k,f[N][N*2];

int main()
{
    cin>>n>>k;
    f[1][0]=1;
    for(int i=2;i<=n;i++)
        for(int j=0;j<=k;j++)
            f[i][j]=(f[i][j-1]-f[i-1][j-i]+f[i-1][j]+mod)%mod;
    cout<<f[n][k]<<endl;
}