做题记录2021.11.3 洛谷P1521逆序对

wuchangjian2021-11-03 21:04:39编程学习

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

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

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

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

相关文章

CSP 201909-4 推荐系统(Python)

题目链接: 计算机软件能力认证考试系统http://118.190.20...

Day_47 初识JavaWeb

Web流程 1.1 软件架构 1. C/S:客户端/服务器端   c...

没有bug队——加贝——Python 练习实例 25,26

我非常认真的告诉大家今天这是一篇水文,别看了 25.题目:...

发表评论    

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。