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

题目描述

��假设我们将序列中第i件物品的参数定义为Ai，那么排序就是指将A1,…,An从小到大排序。若i<j且Ai>Aj，则<i,j>就为一个“逆序对”。SORT公司是一个专门为用户提供排序服务的公司，他们的收费标准就是被要求排序物品的“逆序对”的个数，简称“逆序数”。

��Grant是这家公司的排序员，他想知道对于n个参数都不同的物品组成的序列集合中，逆序对数为t的物品有多少个，并试给出其中一个最小的物品序列。所谓最小，即若有两个物品序列(A1,A2,…,An)，(B1,B2,…,Bn)，存在1≤I≤n，使得(A1,A2,…,Ai-1)＝(B1,B2,…,Bi-1)且Ai＜Bi。

输入输出格式

输入格式：

��即两个整数n和t ( 1≤n≤20，0≤t≤n*(n-1)/2 )。

输出格式：

��第一行表示n个参数都不通的物品组成的序列集合中，逆序数为t的序列个数；

第二行是所求物品参数序列。假设n个物品分别为1到n。

输入输出样例

输入样例#1：复制

4 3

输出样例#1：复制

6
1 4 3 2

洛谷题解：

第一小问动归解决；

第二小问只交换相邻两数达到使逆序对只加一的目的。

时间复杂度O（tn）

 1 #include<cstdio>
 2 #include<cstring>
 3 int i,j,k,n,t,p;
 4 long long f[21][211];
 5 int ans[21];
 6 short rec[21];
 7 int swap(int &a, int &b)
 8 {
 9     int t=ans[a];
10     ans[a]=ans[b];
11     ans[b]=t;
12 }
13 int main()
14 {
15     memset(f,0,sizeof(f));
16     scanf("%d%d",&n,&t);
17     if (n==1)
18     {
19         printf("1
1");
20         return 0;
21     }
22     f[2][1]=1; f[2][0]=1;
23     for (i=3; i<=n; i++)
24         for (j=0; j<=i*(i-1)/2; j++)
25             for (k=0; k<i; k++)
26                 if (j>=k) 
27                    f[i][j]+=f[i-1][j-k];                        
28     printf("%lld
",f[n][t]);
29     for (i=1; i<=n; i++)
30       ans[i]=i;
31     for (i=1; i<=t; i++)
32     {
33         memset(rec,0,sizeof(rec));
34         p=n;
35         rec[ans[p]]=p;
36         while (rec[ans[p-1]+1] == 0) {p--; rec[ans[p]]=p;}
37         int a=p-1,b=rec[ans[p-1]+1];
38         swap(a,b);
39     }
40     for (i=1; i<=n; i++)
41       printf("%d ",ans[i]);
42     return 0;
43 }