这题好像双栈排序呀，所有我直接把代码交了上去，结果...WA

再仔细一看，发现一个秘密：可以有相同的数字。于是，二分图算法的
某些证明失效。怎么办？搜啦！
dfs搜索的过程其实是十分简单的：
首先，模拟两个栈，同时用dfs的方式枚举当前的操作是pop1/pop2/push1/push2
int dfs(int p,int q){
	if (p==N && q==N)return 1;
	if (u && q<N && x[u-1]==B[q]){
		way[p+q]=1;
		u--;
		if (dfs(p,q+1))return 1;
		x[u++]=B[q];
		return 0;
	}
	if (v && q<N && y[v-1]==B[q]){
		way[p+q]=3;
		v--;
		if (dfs(p,q+1))return 1;
		y[v++]=B[q];
		return 0;
	}
	if (p<N && (!u || A[p]<=x[u-1])){
		way[p+q]=0;
		x[u++]=A[p];
		if (dfs(p+1,q))return 1;
		u--;
	}
	if (p<N && (!v || A[p]<=y[v-1])){
		way[p+q]=2;
		y[v++]=A[p];
		if (dfs(p+1,q))return 1;
		v--;
	}
	return 0;
}
这个搜索加了剪枝，但其实还是非常的朴素。然而，把它交上去，得到的是：
TLE?
为什么呢？难道要上强剪枝？我又搜索了网络上某个人给的AC代码。令我意外的是，
他的代码是错的...被我整挂了。不过，他没有用强剪枝，并且我们的代码似乎
唯一一个不同的地方就是他疏忽的那个细节......
不管怎样，我知道了不用强剪枝也是可以过的，那么为什么我的是T的呢？

有些细节决定成败。我试验了一组数据：
44
41 44 43 42 41 40 39 38...1
通过这个数据我了解到了我的代码的一个致命伤：
某些数字放入哪个栈都可以，是对称的，但是如果数据无解，我的代码会拼死了地搜
它究竟应该放在哪个栈里。一个数字这样搜不可怕，一堆数字就使枚举量指数级地增长了。
为了克服这个问题，我又研究了那个错但AC的代码，加了一个小优化：
int dfs(int p,int q){
	//printf("dfs %d %d\n",p,q);
	if (q==N)return 1;
	if (u && x[u-1]==B[q]){
		way[p+q]=1;
		u--;
		if (dfs(p,q+1))return 1;
		x[u++]=B[q];
		return 0;
	}
	if (v && y[v-1]==B[q]){
		way[p+q]=3;
		v--;
		if (dfs(p,q+1))return 1;
		y[v++]=B[q];
		return 0;
	}
	if (p<N && (!u || A[p]<=x[u-1])){
		way[p+q]=0;
		x[u++]=A[p];
		if (dfs(p+1,q))return 1;
		u--;
	}
	if (p<N && (!v || A[p]<=y[v-1]) && (A[p]!=B[q])){
////////////////////////////////////////////////////////////
             优化就在上面一行！
////////////////////////////////////////////////////////////
		way[p+q]=2;
		y[v++]=A[p];
		if (dfs(p+1,q))return 1;
		v--;
	}
	return 0;
}
虽然我知道，这个优化也可以被整残，但是...毕竟它可以AC，还是485MS！
搜索剪枝什么是王道？简单、粗暴、起效。

真正的好的优化我认为应该是：
1.先dp一次判断是否无解，即出现1 4 3 2这种情况
2.通过某种方法，使得在可以同时放在两个栈中的情况下，避免两次搜索，
例如：上面代码的那个优化，即判断如果一个数可以立即入栈再出栈，就放在
第1个栈中，还有：
1 4 3 2 5 5 5 5
这4个5我认为其实可以当做一个5来处理，预处理一下应该有好效果。

• 双栈排序的二分图算法是可以过的，我就过了 (2329) jhfjhfj1 2011-08-01 20:34:09
  • 嗯，很好！ (0) fanhqme 2011-08-02 18:21:17