題目鏈接
這種求方案數(shù)的題一般都是\(dp\)吧。
注意到范圍里\(k\)和\(n\)的范圍一樣大，\(k\)是完全可以更大的，到\(n\)的平方級(jí)別，所以這暗示了我們要把\(k\)寫到狀態(tài)里。
\(f[i][j]\)表示前\(1\)~\(i\)的排列逆序?qū)?shù)為\(j\)的方案數(shù)。
現(xiàn)在考慮把\(i\)插入到\(i-1\)的排列里。
\(i\)肯定是大于\(1\)~\(i-1\)所有數(shù)的，所以插入\(i\)后可以新產(chǎn)生\(0\)~\(i-1\)個(gè)逆序?qū)Α?br /> 于是就能寫出\(O(n^3)\)的\(dp\)算法了。
像這種轉(zhuǎn)移范圍是個(gè)區(qū)間的，要優(yōu)化不是單調(diào)隊(duì)列就是前綴和，當(dāng)然是愉快地選擇后者啦。

#include <queue> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define Open(s) freopen(s".in","r",stdin);freopen(s".out","w",stdout); #define Close fclose(stdin);fclose(stdout); int n, k; int f[1010][1010]; const int MOD = 10000; int main(){scanf("%d%d", &n, &k);f[1][0] = 1;for(int i = 2; i <= n; ++i){int sum = 0;for(int j = 0; j <= k; ++j){sum = (sum + f[i - 1][j]) % MOD;f[i][j] = sum;if(j >= i - 1)sum = ((sum - f[i - 1][j - i + 1]) % MOD + MOD) % MOD;}}printf("%d\n", f[n][k]);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/Qihoo360/p/9901351.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的【洛谷 P2513】 [HAOI2009]逆序对数列（DP）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。