做题记录2021.11.3洛谷P1521逆序对

题目链接
近两天都在写一个C&＃43;&＃43;的Biginteger类&＃xff0c;一直没刷题&＃xff0c;今天补一下。
解法1.纯暴力解法  枚举所有全排列并求其逆序对&＃xff0c;即使采用树状数组等高效方式求逆序对仍要$O(nlogn\ast n!)$&＃xff0c;完全不可行。
解法2.动态规划
定义dp[i][j]为前i个数的全排列中逆序对为j的个数。我一开始是考虑最后一个数字&＃xff0c;但压根没有思路。
正确方法是&＃xff1a;考虑有i-1个数的序列&＃xff0c;将第i个数插入&＃xff0c;由于它是序列中最大的&＃xff0c;所以插入其中最后一个位置&＃xff0c;可以新增0个逆序对&＃xff1b;插入倒数第二个位置新增1个……以此类推&＃xff0c;在最前面可以新增i-1个。&＃xff08;也就是说&＃xff0c;最多可以新增i-1个&＃xff09;。
因此&＃xff0c;dp[i][j]&＃61;dp[i-1]从第j-i-1个到第j个的和。
可以进行一个小小的优化&＃xff1a;不难发现当j>(i−1)(i−2)2j>\frac{(i-1)(i-2)}{2}j>2(i−1)(i−2)​时&＃xff0c;dp[i-1]从(i−1)(i−2)2\frac{(i-1)(i-2)}{2}2(i−1)(i−2)​到j的部分都是0&＃xff0c;因此枚举到前者即可。即
dp[i][j]&＃61;∑k&＃61;max(0,j−i&＃43;1)min(j,cnt(x))dp[i−1][k]dp[i][j]&＃61;\sum \limits_{k&＃61;max(0,j-i&＃43;1)}^{min(j,cnt(x))} dp[i-1][k]dp[i][j]&＃61;k&＃61;max(0,j−i&＃43;1)∑min(j,cnt(x))​dp[i−1][k]&＃xff0c;其中cnt(x)定义见以下代码&＃xff1a;

#include
#include
#define cnt(x) (((x)*(x-1))/2)
#define MOD 10000
const int M&＃61;1001;
using namespace std;
int dp[M][M]&＃61;{{0},{1,0}};
int main() {int n,k;scanf("%d%d",&n,&k);for(int i&＃61;2; i<&＃61;n; i&＃43;&＃43;) dp[i][0]&＃61;1;for(int i&＃61;2; i<&＃61;n; i&＃43;&＃43;) {for(int j&＃61;1; j<&＃61;k; j&＃43;&＃43;) {for(int k&＃61;max(0,j-i&＃43;1); k<&＃61;cnt(i-1)&&k<&＃61;j; k&＃43;&＃43;) {dp[i][j]&＃61;(dp[i][j]&＃43;dp[i-1][k])%MOD;}}}printf("%d",d[n][k]);return 0;
}

其实做到这里&＃xff0c;就不难想到用前缀和优化了。但要注意过程中可能出现负数&＃xff0c;为了方便取模&＃xff0c;这时就不得不将其调整为正数&＃xff0c;而且结果dp[n][k]-dp[n][k-1]仍可能为负数&＃xff0c;也需要做调整。

#include
#include
#define cnt(x) (((x)*(x-1))/2)
#define MOD 10000
const int M&＃61;1001;
using namespace std;
int dp[M][M]&＃61;{{0},{1,0}};
int main() {int n,k;scanf("%d%d",&n,&k);for(int i&＃61;2; i<&＃61;n; i&＃43;&＃43;) dp[i][0]&＃61;1;for(int i&＃61;2; i<&＃61;n; i&＃43;&＃43;) {for(int j&＃61;1; j<&＃61;k; j&＃43;&＃43;) {int right&＃61;min(cnt(i-1),j);if(j-i&＃43;1<&＃61;0) dp[i][j]&＃61;(dp[i][j-1]&＃43;dp[i-1][right])%MOD;else dp[i][j]&＃61;(dp[i][j-1]&＃43;(dp[i-1][right]-dp[i-1][j-i]&＃43;MOD)%MOD)%MOD; //注意负数&＃xff01;}}printf("%d",((dp[n][k]-dp[n][k-1])&＃43;MOD)%MOD); //注意负数&＃xff01;return 0;
}