[vijos1605]——双栈排序

原题
我们可以发现当s[i],s[j]满足一个条件时，s[i],s[j],始终不能进入同一个栈。
这个条件就是存在i<j<k,且s[k]<s[i]<s[j]。将存在该条件的两点连边，构造二分图，之后进行染色，一条边的两端颜色不能相同，否则无解。
判断条件需用DP预处理，否则会TLE，方程为：F[i]=min(s[i],F[i+1]),f[i]为s[i到n]中的最小值，先将f[n+1]设为极大值。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <stack>
#define LL long long
using namespace std;
template <class _T> inline void read(_T &_x) {
	int _t; bool _flag=false;
	while((_t=getchar())!='-'&&(_t<'0'||_t>'9')) ;
	if(_t=='-') _flag=true,_t=getchar(); _x=_t-'0';
	while((_t=getchar())>='0'&&_t<='9') _x=_x*10+_t-'0';
	if(_flag) _x=-_x;
}
const int maxn=2005;
bool Edge[maxn][maxn];
int s[maxn],F[maxn],co[maxn];
stack <int> sa,sb;
int n;
void dfs(int x,int c){
	co[x]=c;
	for(int i=1;i<=n;++i)
		if(Edge[x][i]){
			if(co[i]==c){
				printf("0\n");
				exit(0);
			}
			if(!co[i]) dfs(i,3-c);
		}
}
int main(){
	read(n);
	for(int i=1;i<=n;++i)read(s[i]);
	F[n+1]=0x3f3f3f3f;
	for(int i=n;i>=1;--i)F[i]=min(s[i],F[i+1]);
	for(int i=1;i<n;++i)
		for(int j=i+1;j<=n;++j)
			if(s[i]<s[j]&&F[j+1]<s[i])
				Edge[i][j]=Edge[j][i]=true;
	for(int i=1;i<=n;++i)
		if(!co[i])dfs(i,1);
	int aim=1;
	for(int i=1;i<=n;++i){
		if(co[i]==1){
			sa.push(s[i]);
			printf("a ");
		}
		else{
			sb.push(s[i]);
			printf("c ");
		}
		while(!sa.empty()&&sa.top()==aim||!sb.empty()&&sb.top()==aim){
			if(!sa.empty()&&sa.top()==aim){
				sa.pop();
				printf("b ");
			}
			else{
				sb.pop();
				printf("d ");
			}
			aim++;
		}
	}
	return 0;
}