题解：P2528 [SHOI2001] 排序工作量之新任务

分析

注意到

n\le20

我的第一个反应是搜索，打出暴力发现第一问的答案有规律:

1\\ 1~1\\ 1~ 2~ 2~ 1\\ 1~ 3~ 5 ~6~ 5~ 3 ~1\\ 1~ 4~ 9~ 15~ 20~ 22~ 20~ 15~ 9~ 4 \\

瞪眼大法注意到有

\Large f_{i,j}=f_{i,j-1}+f_{i-1,j}-f_{i-1,j-i}

这样的关系，其中

f_{i,j}

表示有

n

个数，

j

个逆序对的序列数量。

不难发现这就是个容斥原理，所以方程的正确性也是显而易见的了。

对于第二问，硬控了我整整二十分钟，其实这就是个贪心，要求字典序最小的那个序列，所以我们反向对

a_i=i

这个序列进行swap操作，使得它有

t

个逆序对就行了，具体部分看代码。

Code

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=30;int n,t;
int f[N][500];
int a[N],vis[N];
int flag=0,ans2,b[N],num;
signed main(){
	cin>>n>>t;
	for(int i=1;i<=n;i++) a[i]=i;
	f[1][0]=1;
	for(register int i=1;i<=n;i++){
		for(register int k=0;k<=i*(i-1)/2;k++){
			if(k>0 && k-i>=0 )f[i][k]=f[i][k-1]+f[i-1][k]-f[i-1][k-i];
			else if(k>0 && k-i<0) f[i][k]=f[i][k-1]+f[i-1][k];
			else f[i][k]=1;
		}
	}
	cout<<f[n][t]<<endl;
	for(int i=n-1;i>=1;i--){
		for(int j=n;j>i;j--){
            if(num==t){
				for(int i=1;i<=n;i++) cout<<a[i]<<" ";
				return 0; 
			}
            num++;
			swap(a[i],a[j]);
            if(num==t){
				for(int i=1;i<=n;i++) cout<<a[i]<<" ";
				return 0; 
			}
		}
	}
}

题解：P2528 [SHOI2001] 排序工作量之新任务

文章操作

分析

Code

相关推荐

评论

题解：P2528 [SHOI2001] 排序工作量之新任务