M_sea

洛谷2513 [HAOI2009]逆序对数列
题目描述对于一个数列{$a_i$},如果有$i<j$且$a_a_j$,那么我们称$a_i$与$a_j$为一对...
扫描右侧二维码阅读全文
01
2018/11

洛谷2513 [HAOI2009]逆序对数列

题目描述

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

传送门

算法

DP。

设$f[i][j]$表示1~i的排列有j个逆序对的方案个数。

那么枚举i插入的位置,容易得到:

$f[i][j]=\sum\limits_{k=j-i+1}^{j} f[i-1][k]$

到这里已经可以解决P1251 求逆序对了,但要A掉这道题,还需要一些优化。

容易发现上式中的东西是连续的。

那么前缀和搞一搞就行了。

代码

#include <bits/stdc++.h>
#define re register
using namespace std;

const int MOD=10000;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') c=getchar();
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}

int n,k;
int f[1010][1010]; //f[i][j]表示1~n的排列有j个逆序对的方案个数 
int sum[1010];

int main() {
    n=read(),k=read();
    f[0][0]=1;
    for (re int i=0;i<=k;i++) sum[i]=1;
    for (re int i=1;i<=n;i++) {
        for (re int j=0;j<=k;j++) {
            if (j>=i) f[i][j]=(sum[j]-sum[j-i]+MOD)%MOD;
            else f[i][j]=sum[j]%MOD;
        }
        sum[0]=f[i][0]%MOD;
        for (re int j=1;j<=k;j++) sum[j]=(sum[j-1]+f[i][j])%MOD;
    }
    printf("%d\n",f[n][k]);        
    return 0;
}

补充

拿这个代码改一改数组大小就能A掉P1521了。

最后修改:2018 年 11 月 09 日 06 : 07 PM

发表评论