题解 P2513 【[HAOI2009]逆序对数列】

我们令$f[i][j]$表示$i$的全排列中，逆序数为$j$的个数。 我们考虑在$i-1$的排列中插入$i$。$k$是这次更新会导致增加多少逆序数。 则$\begin{aligned}{} f[i][j]=\sum_{k=0}^{\min(i-1,j)}f[i-1][j-k]\end{aligned}$ 自我感觉上面的写法不清真，所以换一个清真的等价写法。 $\begin{aligned}{} f[i][j]=\sum_{k=max(0,j-i+1)}^{j}f[i-1][k]\end{aligned}$ 复杂度：$O(nk^2)$，显然会tle。 我们观察这个式子，k是从0开始循环的，所以我们用前缀和优化dp。 我们开一个变量$\begin{aligned}sum=\sum_{k=max(0,j-i+1)}^jf[i][k]\end{aligned}$ 每次j循环的时候让，把$f[i-1][j]$累加到$sum$，然后让$f[i][j]=sum$即可 但$sum$的求和区间是长度为i的一段f数组，当$j-i+1>=0$的时候sum求和区间的左端点也要离开0，向右移动了，所以加一个右面的$f[i-1][j]$，同时要判断sum的左端点是否大于0，如果是那么就减去左边的$f[i-1][j-i+1]$。(不理解？看下面) ``` 欢迎收看新番：区间先生的旅程 这是我们的主人公[---]：区间先生，长度为5 [---]说他只是一个走过场的区间 t=0, ................ t=1, ]............... t=2, -].............. t=3, --]............. t=4, ---]............ t=5, [---]........... t=6, .[---]..........//注意这里，区间先生的左端点脱离了0 t=7, ..[---].........//未完待续？？？ ... t=?, ...........[---]//因为我们只需要求到k，所以区间先生不用从右端离开，也就不用判断右端是否<=k了 ``` 这就是为什么要加一个if判断一下。 其实这个if可以放到前面的额不过懒得写了 复杂度:$O(nk)$ 总结：以后我们发现有这种累加和的dp方程的时候可以考虑前缀和优化 代码 ```cpp #include <cstdio> #include <iostream> using namespace std; int n, k, p = 10000, f[1010][1010]; int main() { scanf("%d%d", &n, &k); f[1][0] = 1;//初始条件，1的逆序为0，且只有1个排列 for (int i = 2; i <= n; i++) { int sum = 0; for (int j = 0; j <= k; j++) { (sum += f[i - 1][j]) %= p; f[i][j] = sum; if(j >= i - 1)//如果j - i + 1>=0了，sum的求和区间左端点就>=0 (((sum -= f[i - 1][j - i + 1]) %= p)+= p) %= p; } } printf("%d\n", f[n][k]); return 0; } ``` 让我们一起膜拜大佬陈独秀 [安利一发博客](http://www.cnblogs.com/olinr) 空间 @[olinr](https://www.luogu.org/space/show?uid=88460) 还有楼下XKJ大佬