[洛谷]P1521 求逆序对(DP)

发布于 2022-09-24  339 次阅读


题目传送门: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;
}
19岁,性别未知,ACM-XCPC退役选手,CCPC全国邀请赛金牌,ICPC亚洲区域赛银牌,武汉某院校计算机科学与技术专业本科在读。
最后更新于 2022-10-12