CF362 C.Insertion Sort（DP)

CF362C Insertion Sort（DP)

传送门

题意：给一个排列，求对任意两个元素交换后，使总逆序对最小的方案数。

题解：首先要想到交换元素的贡献怎么算。

可以分成5份分析，设x，y交换：

1，p<x

对于p<x的情况，无论后面怎么变，p<x中的逆序对不会改变，对后面元素也不会造成影响。

2，p>y

与上同理

3，p=x

a[x]将换至y处，逆序对因增加x~y中大于a[x]的个数

4，p=y

逆序对减少x~y中大于a[y]的个数

5，x<p<y

对于每个大于a[x]的数 ，逆序对减1

对于每个大于a[y]的数，逆序对加1

然后就很清晰了，n方枚举即可，区间个数可以先dp预处理一下。

#include<iostream>
int n,a[5007];
int f1[5007][5007];
int f2[5007][5007];
int F1(int a,int b,int c){
	return f1[a][c]-f1[b][c];
}
int F2(int a,int b,int c){
	return f2[a][c]-f2[b][c];
}
int cal(int i,int j){
	return -F1(j,i,a[i])+F2(j,i,a[i])+F1(j,i,a[j])-F2(j,i,a[j]);
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	for(int i=1;i<=n;i++){
		for(int j=0;j<n;j++){
			if(a[i-1]>j){
				f1[i][j]=f1[i-1][j]+1;
			}
			else{
				f1[i][j]=f1[i-1][j];
				
			}
			if(a[i-1]<j){
				f2[i][j]=f2[i-1][j]+1;
			}
			else{
				f2[i][j]=f2[i-1][j];	
			}
		}
	}
	int sum=0;
	for(int i=1;i<=n;i++){
		sum+=f1[i][a[i]];
	}
	int mx=0,cnt=0;
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			if(a[i]>a[j]){
				if(cal(i,j)==mx){
					cnt++;
				}
				else if(cal(i,j)>mx){
					cnt=1;
					mx=cal(i,j);
				}
			}
		}
	}
	printf("%d %d
",sum-mx,cnt);
}