隐藏
「BOI2007」名次排序问题 - 未来Dp | Bill Yang's Blog

路终会有尽头，但视野总能看到更远的地方。

0%

「BOI2007」名次排序问题 - 未来Dp

发表于 更新于 分类于 Valine：

题目大意

    给你一个序列$a$，要求对这个序列从大到小排序，每次只能移动一个数到一个位置，每次从$x$位置移动到$y$位置的移动代价是$x+y$，设计一种方案使得移动代价总和最小。

题目分析

此题较难（神奇），听我细细道来。

为了阐述方便，我们求出每个数应该在的位置。
如样例：$20\,30\,5\,15\,10$，每个数应该在的位置：$2\,1\,5\,3\,2$。
记每个数应该在的位置为初始序列$b$，并记录下$b$中每个数所在的位置$pos$。

我们首先证明以下的定理（们）：

引理1

如果我们要移动当前序列中最大的数，则将其一次移动到最后一个位置最优。
证明：
如果我们要移动最大的数，分为两种情况讨论：

  • 往前移动：增加了逆序对，显然不如直接移动到最后。
  • 往后移动到$j(j\lt n)$：再分为两种情况讨论
    • 再移动至少一次到达$n$：显然不优于直接移动到$n$。
    • 通过$j$后面的元素使得$Max$到达$n$：因为$Max$没有移走，因此移动$j$后面的元素的代价比直接移走$Max$增加$1$，因此全部移走的代价增加$n-j$，不优于直接移动到最后。

引理2

如果我们要移动当前序列中最大的数，最先移动它最优。
证明：
考虑不最先移动$Max$的原因：通过移动其他的数使得$Max$在序列中的位置变小，从而移动代价减小。
假设$Max$从$i$位置变为了$j$位置$(i\gt j)$，则代价减少$i-j$。

如图，只有从$A$区移动到$B$区会使得$Max$的位置变小，但是因为$B$区的位置相比于最先移动$Max$增加了$1$，代价至少增加$i-j$。
因此，最先移动$Max$是最优的。

推论3

如果我们要移动当前序列中最大的数，一定最先移动它到最后位置。

定理4

如果我们要移动数$x$，一定最先移动$x$到$x+1$前一位置。
证明：
首先，将$x$移动到$x+1$之后是显然不优的。
由推论$3$可知，如果$x$的位置小于$x+1$的位置，一定最先移动$x$到$x+1$前一位置。

若$x$的位置大于$x+1$的位置，如图：

若不最先移动$x$，分类讨论：

  • 我们不会将$A$区的元素移动到别处，这样显然不优。
  • 我们同样不会将$B$区的元素移动到$C$区，显然不优。
  • 若将$C$区的元素移动到$B$区，其代价比先移动$x$小$1$，假设移动了$num$个，代价总计小$num$，但移动$x$的时候代价至少增加了$num$，不优。
  • 若将$B$区的元素移动到$A$区，原因与上类似。
  • 若将$C$区的元素移动到$A$区，移动$x$时代价增加，显然不优。

综上，我们一定会先移动$x$。
根据引理$1$可知一定将其移动到$x+1$前。

因此，定理得证。

有了这些定理（们），我们可以知道这样的结论：如果要移动一个数，一定移动到比他大$1$的元素前一个。但这是基于需要移动它，我们也可以不移动它，留给比他小的元素移动使其被动移动到目标位置。

假设每个数必须移动，根据定理可知，我们按照编号从大到小依次将每个数$x$移动到$x+1$前面，但因为移动的时候每个数的位置都在改变，不方便计算代价，不妨作以下变形。

我们移动一个数$x$到达位置$p$，不改变其余数的位置，令$x$与原在$p$的数共用位置$p$。称这样的序列为改造序列$d$。
我们需要快速的根据改造序列算出每个数在原序列中的位置，方便计算代价。
设$c(p,x)$为按照顺序移动过程中，数$x$在改造序列中位置为$p$，其在原序列中的位置。
因为我们是从大到小移动$x$，故比$x$大的元素不可能在$x$之前，所以$c(p,x)=\sum_{i=1}^p [d[i]\lt x]$。
因为从大到小移动$x$，转移只可能发生在$x+1$与$x$之间，故还可以记为$c(p,x)=\sum_{i=1}^{p} [b[i]\lt x]$。

设$f[x,p]$表示将$x$移动到改造序列的$p$位置的最小代价和。
因此，$f[x,p]=f[x+1,p]+c(pos[x],x)+c(p,x+1)-1\quad(p\gt pos[x])$。
$c$的计算可以边转移边得出（见代码）。

接下来我们考虑不移动数$x$，因为$x$不移动，因此对$x$位置以后的位置$p$，数$i(i\lt x)$，$c(p,i)$的值应该增加$1$。

因此，当前不移动数$x$后对未来造成后效性，我们是否不能做了呢？
不妨将后效性的代价加入到当前决策计算。

$x$不移动，则比$x-1$必须要移动到$x$前，对于$x$位置以后的位置$p$，数$i(i\lt x)$，要移动$i$时，$c(p,i)$的值应该增加$x-i$。
因为上述转移方程是线性的，且如果$x$不移动，对于之后所有小于其的数的代价必定会增加，我们可以将$f+c+\delta_c$的代价算作$(f+\delta_c)+c$，故将$c$的偏差量加入$f$计算。


还是这个图，我们只需要加上$x$到$x+1$的所有数的偏差代价。
为什么不增加$x+1$以后的代价？
若$x+1$以后也有数比$x$小，说明$x+1$仍未移动，这样$x+1$后面的数的代价已经被$x+1$累计，不需重复计算。

故我们可以在算完移动$x$后的状态后做这样一件事情：

1
2
3
4
5
int c=0;
for(int j=pos[i]+1; j<=n+1; j++) {
	f[i][pos[i]]=min(f[i][pos[i]],f[i+1][j]+c);
	if(b[j]<i)c+=i-b[j];
}

最后答案等于：$\min(f[1,i])$，因为$f[1,i]$中$i$表示的是改造数组中$1
的位置，故不需要再计算$1$移动的代价。

代码

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
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}

const int maxn=1005;

int n,a[maxn],b[maxn],pos[maxn];

void Discretization() {
	memcpy(b,a,sizeof(b));
	sort(a+1,a+n+1);
	int cnt=unique(a+1,a+n+1)-a-1;
	for(int i=1; i<=n; i++)b[i]=lower_bound(a+1,a+cnt+1,b[i])-a;
}

int main() {
	n=Get_Int();
	for(int i=1; i<=n; i++)a[i]=Get_Int();
	Discretization();
	for(int i=1; i<=n; i++) {
		b[i]=n-b[i]+1;
		pos[b[i]]=i;
	}
	memset(f,0x3f,sizeof(f));
	f[n+1][n+1]=0;
	for(int i=n; i>=1; i--) {
		int c1=1,c2=1;
		for(int j=1; j<pos[i]; j++)
			if(b[j]<i)c1++;
		for(int j=1; j<=n+1; j++) {
			f[i][j]=f[i+1][j]+c1+c2-1;
			if(b[j]<i+1)c2++;
		}
		int c=0;
		for(int j=pos[i]+1; j<=n+1; j++) {
			f[i][pos[i]]=min(f[i][pos[i]],f[i+1][j]+c);
			if(b[j]<i)c+=i-b[j];
		}
	}
	int ans=INT_MAX;
	for(int i=1; i<=n+1; i++)ans=min(ans,f[1][i]);
	printf("%d\n",ans);
	return 0;
}

参考文献

  • 徐源盛《对一类动态规划问题的研究》
  • BOI2007题目讨论
相关文章
姥爷们赏瓶冰阔落吧~