P7796 [COCI2014-2015#7] POLICE

图书馆里有 \(n\) 个书架，每个书架可以放 \(m\) 本书。小C是一位优秀的图书管理员，所以他决定整理图书馆中的所有图书，如果可以的话，把所有图书放回它们原来的位置。他打算用下面的方法来整理图书：

1.如果书架上的某本书的左边或右边是空的，就可以把这本书书向左或向右移动。

2.把一本书从书架上拿起来，再放回到另一个空的位置（可以是任意一个书架）。

可是没过多久小 C 就累了。如果他手上已经有了一本书，他就不能再移动其他的书。而且因为把书拿出来又放回去实在太麻烦了，所以小 C 希望尽可能少地将书从书架上拿起来（即步骤2）。请帮小 C 算出，他最少需要将书拿出来多少次。

\(1\leq n,m\leq 1000\)

感觉做法挺奇妙的 .

一行一行地考虑 .

先考虑当前行和最终行出现书本相同的情况 . 此时，又分出来两种 ，有空位和无空位 .

1. 有空位，相当于，找到一本书，再放到它原本的位置上 . 那么，要选出 \(k\) 本书，这 \(k\) 本书相对顺序是正确的，其他的书要根据这 \(k\) 本书的位置放入 . 会发现，这是一个 lis 的问题 . 那么，可以 \(O(n\log n)\) 地解决.
2. 没有空位，此时分为两种情况 .
   • 当前行与目标行相同 . 无需操作 .
   • 当前行与目标行不同，如果其他书架上没有空位，则输出 -1 . 否则，将当前行中一本不位于 \(k\) 本书中的书放到其他书架上，再将当前行排序，排完序后直接插入正确的位置，时间复杂度为 \(O(n\log n)\) .

考虑玩当前行和最终行出现书本相同的情况，下面就是不同的 .

如果最终应该出现在第 \(j\) 行的书出现在了第 \(i\) 行，那么，由 \(i\) 向 \(j\) 连一条有向边 ，得到一个有向图 \(G_1\) ；将 \(G_1\) 中的有向边变成无向，可以得到一个无向图 \(G_2\) . 对于 \(G_2\) 中的每一个连通块，在 \(G_1\) 中可以加上一些虚构的有向边，是的其变成一个具有欧拉回路的图 .

那么，对于这个欧拉回路，就是一个移动的方案，但是，这个方案的开始，必定是存在一个连通块中的行有一个空位 . 如果其他的行没有空位的话，那么，必定是不可行的，要输出 -1 .否则，如果连通块不存在空位，需要拿出一本书放在另一行中，然后再移动 ，代价加 \(1\) .

因为从当前书架拿起，放到其他书架的书必定花费代价 \(1\) ，而且必定会放到正确的相对位置上 . 代价就是原来就同时存在与当前和最终行中的书的和 - 当前和最终行中的书的和的 lis + 在最终行但不在当前行的书的数量 . 再加上启动时可能需要的 \(1\) 代价.

时间复杂度 : \(O(nm\log n)\)

空间复杂度 : \(O(nm)\)

code

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	char ch=getchar();
	while(ch<‘0‘||ch>‘9‘)ch=getchar();
	int res=0;
	while(ch>=‘0‘&&ch<=‘9‘){
		res=res*10+ch-‘0‘;
		ch=getchar();
	}
	return res;
}
inline void print(int res){
	if(res==0){
		putchar(‘0‘);
		return;
	}
	int a[8],len=0;
	while(res>0){
		a[len++]=res%10;
		res/=10;
	}
	for(int i=len-1;i>=0;i--)putchar(a[i]+‘0‘);
}
const int inf=1e9+10;
int n,m;
int a[1010][1010],b[1010][1010],nu[1010*1010];
int pos[1010*1010];
bool ok[1010],spare=false;
int exist[1010*1010];
int ans=0;
int bit[1010];
inline void upd(int i,int val){
	while(i<=m){
		bit[i]=max(bit[i],val);
		i+=i&-i;
	}
}
inline int qry(int i){
	int res=0;
	while(i){
		res=max(res,bit[i]);
		i-=i&-i;
	}
	return res;
}
vector<int>v,g[1010];
bool vis[1010];
void dfs(int x){
	vis[x]=true;v.push_back(x);
	for(int i=0;i<(int)g[x].size();i++){
		int to=g[x][i];
		if(!vis[to])dfs(to);
	}
}
int solve(int id){
//	cout<<endl;
//	for(int i=0;i<m;i++)cout<<a[id][i]<<" ";cout<<endl;
//	for(int i=0;i<m;i++)cout<<b[id][i]<<" ";cout<<endl;
	int cnt=0;
	for(int i=0;i<m;i++)if(a[id][i]>0)nu[a[id][i]]=cnt++;
	for(int i=0;i<=m;i++)bit[i]=0;
	for(int i=0;i<m;i++)if(b[id][i]>0)
		upd(nu[b[id][i]]+1,qry(nu[b[id][i]])+1);
	int mx=0;
	for(int i=1;i<=cnt;i++)mx=max(mx,qry(i));
	return mx;
}
int na[1010],nb[1010];
void solve(vector<int>v){
	bool sp=false;
	for(int i=0;i<(int)v.size();i++){
		int id=v[i];
		for(int j=0;j<m;j++)if(a[id][j]==0)sp=true;
	}
	int cnt=0;
	for(int i=0;i<(int)v.size();i++){
		int id=v[i];
		for(int j=0;j<m;j++)if(a[id][j]>0)exist[a[id][j]]++,cnt++;
		for(int j=0;j<m;j++)if(b[id][j]>0)exist[b[id][j]]++;		
		for(int j=0;j<m;j++)na[j]=a[id][j];
		for(int j=0;j<m;j++)nb[j]=b[id][j];
		for(int j=0;j<m;j++)if(a[id][j]>0&&exist[a[id][j]]<2)a[id][j]=0;
		for(int j=0;j<m;j++)if(b[id][j]>0&&exist[b[id][j]]<2)b[id][j]=0;
		ans-=solve(id);
		for(int j=0;j<m;j++)a[id][j]=na[j];
		for(int j=0;j<m;j++)b[id][j]=nb[j];
		for(int j=0;j<m;j++)if(a[id][j]>0)exist[a[id][j]]--;
		for(int j=0;j<m;j++)if(b[id][j]>0)exist[b[id][j]]--;
	}
//	putchar(‘\n‘);
	ans+=cnt;
	if(!sp){
		if(!spare){
			putchar(‘-‘);
			putchar(‘1‘);
			exit(0);
		}
		else ans++;
	}
}
int main(){
//	freopen("test.txt","r",stdin);
	n=read();m=read();
	for(int i=0;i<n;i++)for(int j=0;j<m;j++)a[i][j]=read();
	for(int i=0;i<n;i++)for(int j=0;j<m;j++)b[i][j]=read();
	for(int i=0;i<n;i++)for(int j=0;j<m;j++)if(a[i][j]==0)spare=true;
	for(int i=0;i<n;i++){
		bool flag=true;
		int cnt=0;
		for(int j=0;j<m;j++){
			if(a[i][j]>0){
				exist[a[i][j]]=true;
				cnt++;
			}
		}
		for(int j=0;j<m;j++){
			if(b[i][j]>0){
				if(!exist[b[i][j]])
					flag=false;
				else exist[b[i][j]]=false;
			}
		}
		for(int j=0;j<m;j++){
			if(exist[a[i][j]]){
				flag=false;
				exist[a[i][j]]=false;
			}
		}
		if(flag){
			ok[i]=true;
			int tmp=cnt-solve(i);
			ans+=tmp;
			if(cnt==m&&tmp!=0){
				if(!spare){					
					putchar(‘-‘);
					putchar(‘1‘);
					return 0;
				}
				else ans++;
			}
		}
	}
//	for(int i=0;i<n;i++)print(ok[i]),putchar(‘ ‘);
//	putchar(‘\n‘);
	for(int i=0;i<n;i++)for(int j=0;j<m;j++)if(a[i][j]>0&&(!ok[i]))pos[a[i][j]]=i;
	for(int i=0;i<n;i++)for(int j=0;j<m;j++){
		if(b[i][j]>0&&(!ok[i])&&pos[b[i][j]]!=i){
		//	print(pos[b[i][j]]);putchar(‘ ‘);print(i);putchar(‘\n‘);
			g[pos[b[i][j]]].push_back(i);
			g[i].push_back(pos[b[i][j]]);
		}
	}
	for(int i=0;i<n;i++)if((!ok[i])&&(!vis[i])){
		v.clear();
		dfs(i);
	//	for(int j=0;j<(int)v.size();j++)print(v[j]),putchar(‘ ‘);
		solve(v);
	}	
	print(ans);
	return 0;
}
/*inline? ll or int? size? min max?*/

P7796 [COCI2014-2015#7] POLICE

原文：https://www.cnblogs.com/suadwm/p/15212332.html