OI题解 - Desant(LOJ) | Lucky_Glass's Blog

以心为名，名为爱惜

0%

OI题解 - Desant(LOJ)

发表于 分类于 Valine：

一道自己非常想做的题（但是好难啊……还是不能独立想出来）

# 题面

> LOJ 3217

# 解析

显然是DP，而且 $n$ 很小容易往状压这个方向想。虽说是状压，但也不是简单的 $2^n$ 状压能够解决的。

我们考虑从左到右决策每个 $a_i$ 是否选入子序列。但是我们还要能够从状态计算出新增的逆序对的数量，于是考虑再加一维状态压缩 $S$。

> Tab. 注意下文中提到的“数字”和“位置”的区分，“位置i”指的是数组中的 $a_i$

下面来具体阐述一下 $S$ 的定义：

  • 对于每个数字定义 unfix[i] 表示 “数字i 是否选入子序列”是否已经确定（=true 是不确定）。我们从左到右决策每个位置i，如果位置i已经被决策，则数字$a_i$则是确定的。
  • 在数轴上，考虑没有确定的数字把数轴分成若干段，储存每一段中被选入序列的数字的数量。
  • $S$ 即“储存每一段中已经确定的数字的数量”状压的结果。

（难点主要就是定义……）

考虑如何转移：

  • 先枚举 $S$，然后把 $S$ 还原成数组；
  • 当我们决策了位置i后，$a_i$ 变为确定，则数组需要合并两个相邻元素；
  • 如果 $a_i$ 要选入序列，则对应段的选入序列的数字数量+1，增加的逆序对的数量为数轴上比 $a_i$ 大的选入序列的数的数量；
  • 如果不选入序列，则直接更新答案。

# 源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
/*Lucky_Glass*/
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

typedef long long ll;
const int N=43,INF=(1<<29);

struct DATA{
	int val;ll num;
	DATA(){}
	DATA(const int _v,const ll _n):val(_v),num(_n){}
};
DATA Update(const DATA &A,const DATA &B){
	if(A.val==B.val) return DATA(A.val,A.num+B.num);
	return A.val<B.val? A:B;
}

int n,A[N];
bool unfix[N];
vector<int> per[2],mul[2];
vector<DATA> f[2];
vector<int> ary;
DATA ans[N];

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&A[i]);
		A[i]--,unfix[A[i]]=true;
		ans[i]=DATA(INF,0);
	}
	f[0].push_back(DATA(0,1));
	mul[0].push_back(1);
	for(int i=0;i<=n;i++){
		per[0].push_back(1);
		mul[0].push_back(mul[0].back()*per[0].back());
	}
	for(int i=1,I=1;i<=n;i++,I^=1){
		per[I].clear(),mul[I].clear();
		int pos=0;
		for(int j=0;j<A[i];j++)
			pos+=unfix[j];
		unfix[A[i]]=false;
		mul[I].push_back(1);
		int las=-1;
		for(int j=0;j<n;j++)
			if(unfix[j]){
				per[I].push_back(j-las);
				mul[I].push_back(mul[I].back()*per[I].back());
				las=j;
			}
		per[I].push_back(n-las);
		mul[I].push_back(mul[I].back()*per[I].back());
		f[I]=vector<DATA>(mul[I].back(),DATA(INF,0));
		int J=!I,sizI=per[I].size(),sizJ=per[J].size();
		for(int S=0;S<mul[J].back();S++){
			if(!f[J][S].num) continue;
			ary.clear();
			//Transform from last array to now
			//1. Uncode the array
			for(int j=0,tmp=S;j<sizJ;j++)
				ary.push_back(tmp%per[J][j]),tmp/=per[J][j];
			//2. Culculate the new pairs(If choose A[i])
			int add=0;
			for(int j=pos+1;j<sizJ;j++)
				add+=ary[j];
			//3. The statue of A[i] is fixed
			ary[pos]+=ary[pos+1];
			ary.erase(ary.begin()+pos+1);
			//4. Recode the array
			int toS=0;
			for(int j=0;j<sizI;j++)
				toS+=mul[I][j]*ary[j];
			//Not choose A[i]
			f[I][toS]=Update(f[I][toS],f[J][S]);
			//Choose A[i]
			toS+=mul[I][pos];
			DATA tmpd=f[J][S];
			tmpd.val+=add;
			f[I][toS]=Update(f[I][toS],tmpd);
		}
	}
	int I=n&1,sizI=per[I].size();
	for(int S=0;S<mul[I].back();S++){
		if(!f[I][S].num) continue;
		int cnt=0;
		for(int tmp=S,j=0;j<sizI;j++)
			cnt+=tmp%per[I][j],tmp/=per[I][j];
		ans[cnt]=Update(ans[cnt],f[I][S]);
	}
	for(int i=1;i<=n;i++)
		printf("%d %lld\n",ans[i].val,ans[i].num);
	return 0;
}

THE END

Thanks for reading!