OI - Ranklist Sorting(BZOJ) | Lucky_Glass's Blog

以心为名，名为爱惜

0%

OI - Ranklist Sorting(BZOJ)

发表于 更新于 分类于 Valine：

SPOJ 的数据是不是有问题啊……
看起来像没有 SPJ 的样子

# 题面

> Linked DarkBZOJ 1431

点击展开/折叠 题面

有 $n$ 个互不相同的数字，你可以花费 $i+j$ 的代价将当前位置为 $i$ 的数挪动到 $j$ 位置上。

最后要把数列变为单调递减，求最小代价。

$n\le1000$

# 解析

由于我一开始读错题了……写的是最后把数列变成单调递增，下面博客的思路也是按照单调递增的写的

数字互不相同，可以先离散化成 $1\sim n$ 的排列。

首先有几个感性理解非常容易，但是真正证明还挺麻烦的结论：

结论1

一个数如果要挪动，一定只挪动一次。

结论2

一定存在一种最优解，满足每次挪动的数的大小递减。

两个结论分开来并不容易证明，但是可以合在一起归纳证明。先考虑最大的数，它的目标位置是 $n$，假如它要挪动，但是先挪到 $i(i< n)$。接下来两种方案：

  • 要么位置在 $[i+1,n]$ 的这些数都向前挪（不可能 $[i+1,n]$ 部分向前挪，这样最大值仍需移动，且移动的代价增大）；
  • 要么最大值再挪动；

相较于直接挪动到 $n$：第一种方案 $[i+1,n]$ 的移动代价都增大了 $1$，第二种方案最后得到的数列完全相同，但是花费更大。所以最大值要挪动就直接“一步到位”。

也因为最大值先移动可以使最大值原位置和 $n$ 之间的数移动的代价至少减少 $1$，能贪心地得到最优解。

综上，如果最大值要移动，则第一个移动且直接移动到末尾；此时最大值对移动代价的影响已经固定，可以“删去”最大值归纳证明子问题。

那么我们从大到小考虑每个数怎么移动，记现在正在考虑数字 $i$ 怎么移动：

  • 如果数字 $i$ 要移动，则一定挪动到 $i+1$ 前面一个位置；
  • 如果数字 $i$ 已经在 $i+1$ 前面（不一定紧挨着），可以选择不挪动 $i$——此时位置在 $i$ 和 $i+1$ 之间的数必须移动到 $i$ 前面。

考虑了数字 $i$ 的移动后，$i\sim n$ 的相对位置应该是递增的，并且由于只移动了 $i\sim n$，$1\sim i-1$ 的相对位置和初始数列一样。

记 $r_i$ 表示在 $\le i$ 的数的子序列中 $i$ 的位置；

记 $A_i$ 表示 $\le i$ 的数的子序列，$A_i[j]$ 表示 $A_i$ 的从位置 $j$ 开始的后缀。

显然“必须要移动的数”在 $A_{i-1}$ 中表现为一段后缀，即位置在 $i$ 之后的所有 $< i$ 的数字。于是可以设计 DP 状态 $f_{i,j}$ 表示，已经考虑了 $i\sim n$ 的挪动方案，此时 $A_{i-1}$ 中，位置 $j$ 及以后的数字必须移动。

由于 $< i$ 的数的相对位置和初始时相同，而 $< i$ 的子序列中位置小于 $j$ 的数字都在 $i$ 前面，数字 $i$ 现在的位置 恰好就是 $j$。

接下来再讨论几种转移：

  • 若数字 $i$ 在 $i+1$ 前面，在 DP 状态中体现为“$i$ 不是必须移动的数字”，则有两种转移：
    • $i$ 不移动，则 $r_i$ 之后的 $< i$ 的数（$A_i[r_i+1]=A_{i-1}[r_i]$）都必须移动到 $i$ 前面，转移到 $f_{i,r_i}$；
    • $i$ 移动到 $i+1$ 前面一个位置，此时必须要挪动的数没有新增（$A_{i}[j]=A_{i-1}[j-1]$），转移到 $f_{i,j-1}$；
  • 若数字 $i$ 在 $i+1$ 后面，则必须要移动到 $i+1$ 前面一个位置。必须要挪动的数没有新增（$A_{i}[j]=A_{i-1}[j]$），转移到 $f_{i,j}$。

还要计算转移的额外代价——挪动 $i$ 时，我们知道 $i+1$ 的真实位置为 $j$，但是我们不知道 $i$ 的真实位置，只知道它在 $A_i$ 中的相对位置。所以我们希望通过相对位置来求得答案。

这就要用到 费用提前计算，注意到 $i$ 在 $A_i$ 中的相对位置与其真实位置相差只有位置在 $i$ 前面并且没有挪动的 $\ge i+1$ 的数的数量。而如果 $i$ 之前有 $\ge i$ 且没有挪动的数，$i$ 是一定要挪动的。所以我们只要在每次决定数 $i$ 不挪动时，将 $i$ 后面 $< i$ 的数的转移代价 $+1$ 即可。

于是上述的三种转移具体为：

  • 若 $r_i< j$，则 $i$ 不必要移动：

    • 若 $i$ 不移动，会使 $A_{i-1}[r_i]$ 这些数的转移的代价加一：

      $f_{i+1,j}+(i-1-r_i+1)\to f_{i,r_i}$；

    • 若 $i$ 移动，会使 $A_{i-1}[j-1]$ 的转移代价加一，且移动本身产生代价为 $i+1$ 的真实位置 $j$ 和 $i$ 在 $A_i$ 的相对位置 $r_i$：

      $f_{i+1,j}+(i-j+1)+(j-1+r_i)\to f_{i,j-1}$

      Hint. $(j-1+r_i)$ 的减一是因为移动到 $i+1$ 的前面；

  • 若 $r_i\ge j$，则 $i$ 必须移动到 $i+1$ 前面一个位置；

    移动代价为 $j+r_i$，会使 $A_{i-1}$ 中 $r_i$ 到 $j-1$ 的转移代价加一：

    $f_{i+1,j}+(j+r_i)+(r_i-j)\to f_{i,j}$

最后要输出方案就储存一下转移点。

# 源代码

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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=1e3+10;
#define minc(a,b) (a=min(a,b))

struct TREEARRAY{
	#define lowbit(x) ((x)&(-(x)))
	int ary[N],siz;
	void Init(int n){
		for(int i=1;i<=n;i++) ary[i]=0;
		siz=n;
	}
	void Modify(int pos,int val){
		while(pos<=siz){
			ary[pos]+=val;
			pos+=lowbit(pos);
		}
	}
	int Query(int pos){
		int ret=0;
		while(pos){
			ret+=ary[pos];
			pos-=lowbit(pos);
		}
		return ret;
	}
	#undef lowbit
}Ta;

int num[N],uni[N],f[N][N],rnk[N],n;
bool mov[N][N],tmov[N];
int to[N][N];

bool Transform(int p,int q,int tp,int tq,int add){
	if(f[p][q]+add<f[tp][tq]){
		f[tp][tq]=add+f[p][q];
		return true;
	}
	return false;
}
int main(){
	while(~scanf("%d",&n)){
		for(int i=1;i<=n;i++)
			scanf("%d",&num[i]),uni[i]=num[i];
		sort(uni+1,uni+1+n);
		Ta.Init(n);
		for(int i=1;i<=n;i++){
			num[i]=n+1-int(lower_bound(uni+1,uni+1+n,num[i])-uni);
			Ta.Modify(num[i],1);
			rnk[num[i]]=Ta.Query(num[i]-1)+1;
			// printf("%d ",rnk[i]);
		}
		// printf("\n");
		memset(f,0x3f,sizeof f);
		int inf=f[0][0];
		f[n+1][n+1]=0;
		for(int i=n;i>=1;i--)
			for(int j=1;j<=i+1;j++){
				//j=pos[i+1]="A[j~i] have to move"('A' is the sequence of numbers <=i)
				if(f[i+1][j]==inf) continue;
				if(rnk[i]<j){ //i don't have to move
					//not move i:
					//1. numbers <i and after i - the st-position +1
					//2. numbers <i and after i have to move
					if(Transform(i+1,j,i,rnk[i],i-rnk[i]))
						mov[i][rnk[i]]=false,to[i][rnk[i]]=j;
					//move i:
					//1. numbers <i and after i+1 - the st-position +1
					//2. the cost of moving i is 'rnk[i](relative position of i) + j(real position of i+1) - 1'
					if(Transform(i+1,j,i,j-1,(i-j+1)+(rnk[i]+j-1)))
						mov[i][j-1]=true,to[i][j-1]=j;
				}
				else{
					//must move i
					//1. the cost of moving i
					//2. (relative position) after j
					if(Transform(i+1,j,i,j,(i-j)+(rnk[i]+j)))
						mov[i][j]=true,to[i][j]=j;
				}
			}
		for(int i=1,j=1;i<=n;i++){
			tmov[i]=mov[i][j];
			j=to[i][j];
		}
		int nans=0;
		for(int i=n;i;i--)
			if(tmov[i]){
				int pi,pi1=n+1;
				for(int j=1;j<=n;j++){
					if(num[j]==i) pi=j;
					if(num[j]==i+1) pi1=j;
				}
				if(pi<pi1){
					nans++,f[nans][0]=pi,f[nans][1]=pi1-1;
					for(int j=pi;j<pi1-1;j++)
						swap(num[j],num[j+1]);
				}
				else{
					nans++,f[nans][0]=pi,f[nans][1]=pi1;
					for(int j=pi;j>pi1;j--)
						swap(num[j],num[j-1]);
				}
			}
		printf("%d\n",nans);
	}
	return 0;
}

THE END

Thanks for reading!