P7796 [COCI2014-2015#7] POLICE

题目大意

有 $n$ 个书架，每个书架有 $m$ 个位置，现在第 $i$ 个书架上第 $j$ 个位置放着编号为 $a_{i,j}$ 的书，$a_{i,j}=0$ 表示这个位置没有书，目标是把第 $i$ 个书架上第 $j$ 个位置书架上书的状态变为 $b_{i,j}$，有这样两个操作：

• 如果左边或右边有空位，可以在书架上向左或向右移动图书，不耗费代价。
• 从书架上取下一本书放在空位上，耗费一代价。

求变为目标状态最少耗费多少代价。

思路

先考虑特殊性质。保证每本书在初始和最终状态下都会在同一个书架上时，把书按照目标状态上的书架从左到右按顺序标号，这样每本书都有它的编号。每一个书架上不需要被移动的书是编号在初始书架的最长上升子序列中的书，其它的书本都是需要被移动的。求有几本书不需要被移动实际上就是求原书架的 LIS 就行了。

再考虑一般情况。一本书如果要移动到其它书架上，假设它从 $i$ 书架一道 $j$ 书架上，那么往点 $i$ 到点 $j$ 连一条边。可以发现，对于一个连通块，总可以找到一种移动方法来让书移动到正确的地方。一开始启动的时候要有一个空位，那么如果一个连通块没有空位，就要额外移动一次去创造一个空位。连通块有没有空位可以用并查集维护。如果一本书开始时在哪个书架最后就在哪个书架，那么把这些书单独拿出来，做一遍特殊性质。

所以最后的答案就是：书的本数 - 每一行的 LIS + 启动代价。

代码

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define N 1099
using namespace std;
typedef long long ll;
char chart; bool fushu;
template <typename T> void read(T &a) { a=fushu=0; do chart=getchar(); while((chart<48||chart>57)&&chart!='-'); if(chart=='-') fushu=1,chart=getchar(); do a=(a<<1)+(a<<3)+(chart^48),chart=getchar(); while(chart>47&&chart<58); if(fushu) a=-a; return ; }
template <typename T,typename ...Args> void read(T &a,Args &...args) { read(a); read(args...); return ; }
int n,m,a[N][N]={},b[N][N]={},v[N*N]={},ceng[N*N]={},cnt[N]={},cv=0,fa[N]={},tag[N]={},ans=0;
struct BITS {
	#define lowbit(x) ((x)&-(x))
	int tr[N*4];
	int get(int x) {
		int rey=0;
		while(x)
			rey=max(rey,tr[x]),
			x-=lowbit(x);
		return rey;
	}
	void put(int x,int val) {
		while(x<=m)
			tr[x]=max(tr[x],val),
			x+=lowbit(x);
		return ;
	}
	#undef lowbit
};
int lis(int u)
{
	int i,x,dp,rey=0;
	BITS f={};
	for(i=1;i<=m;++i)
		if(a[u][i]&&ceng[a[u][i]]==u) {
			x=v[a[u][i]];
			dp=f.get(x-1)+1;
			rey=max(rey,dp);
			f.put(x,dp);
		}
	return rey;
}
int father(int x) { return fa[x]=fa[x]==x?x:father(fa[x]); }
void link(int x,int y) { fa[father(x)]=father(y); return ; }
bool ok()
{
	int i,j;
	for(i=1;i<=n;++i)
		for(j=1;j<=m;++j)
			if(a[i][j]!=b[i][j])
				return false;
	return true;
}
bool oks(int x)
{
	int i;
	for(i=1;i<=m;++i)
		if(a[x][i]!=b[x][i])
			return false;
	return true;
}
int main()
{
//	freopen("librarian.in","r",stdin);
//	freopen("librarian.out","w",stdout);
	int i,j,ckflag=0;
	read(n,m);
	for(i=1;i<=n;++i) {
		for(j=1;j<=m;++j) {
			read(a[i][j]);
			if(a[i][j])
				++cnt[i];
		}
		if(cnt[i]!=m) ckflag=true;
	}
	for(i=1;i<=n;++i) {
		for(j=1;j<=m;++j) {
			read(b[i][j]);
			if(b[i][j])
				v[b[i][j]]=++cv,
				ceng[b[i][j]]=i;
		}
		fa[i]=i,tag[i]=0,ans+=cv,cv=0;
	}
	if(!ckflag) {
		if(ok()) printf("0");
		else printf("-1");
		return 0;
	}
	for(i=1;i<=n;++i)
		for(j=1;j<=m;++j)
			link(i,ceng[a[i][j]]);
	for(i=1;i<=n;++i)
		if(cnt[i]!=m)
			tag[father(i)]=true;
	for(i=1;i<=n;++i) {
		ans-=lis(i);
		if(i==father(i)&&!tag[i]&&!oks(i))
			++ans;
	}
	printf("%d",ans);
}

时空复杂度

时间复杂度 $O(nm \log m)$。

空间复杂度 $O(nm)$。