题目传送门:P1521 求逆序对 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
思路 / Thought
用dp[i]j[j]表示选取[1, i]的数组,且有j个逆序对的排列方案数。
dp[i]可以从dp[i - 1]转移过来,假设现在的数字是i,那么对于dp[i - 1]的所有状态,i可以插入到i个位置中去,如果插入到第1个位置,那么逆序对会增加i - 1个,如果插入第2个位置,逆序对会增加i - 2个,如果插入到第i个位置,逆序对会增加i个。
所以dp[i][j]的状态可以从dp[i - 1][j]....dp[i - 1][j - i + 1]转移过来。
代码 / Code
#include <bits/stdc++.h> #define int long long using namespace std; const int maxn = 103; int dp[maxn][maxn * maxn]; signed main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int N, K;cin >> N >> K; dp[0][0] = 1; for(int i = 1;i <= N; ++ i) { for(int j = 0;j <= K; ++ j) { //插入到第l位 for(int l = i;l >= 1 && j - i + l >= 0; -- l)dp[i][j] += dp[i - 1][j - i + l]; dp[i][j] %= 10000; } } cout << dp[N][K] << '\n'; return 0; }
Comments NOTHING