学步园

//如果队列inSeq中存在i<j<k，使得inSeq[k]<inSeq[i]<inSeq[j]，那么inSeq[i]和inSeq[j]不能被放进同一个栈中<br /> #include <iostream><br /> #include <stack><br /> #include <cmath><br /> #include <cstring><br /> #include <string><br /> using namespace std;<br /> #define INF 10000<br /> int color[1010];<br /> bool adj[1010][1010];<br /> int _min[1010];<br /> int n;<br /> int inSeq[1010];<br /> stack<int> s1;<br /> stack<int> s2;<br /> string path;<br /> bool dfs(int cur) {<br /> for(int i = 0; i < n; i++) {<br /> if(adj[cur][i]) {<br /> if(color[i] == 0) {<br /> color[i] = 3 - color[cur];<br /> if(!dfs(i)) return false;<br /> }else if(color[i] == color[cur]) return false;<br /> }<br /> }<br /> return true;<br /> }<br /> int main() {<br /> //freopen("1.txt", "r", stdin);<br /> while(cin >> n) {<br /> for(int i = 0; i < n; i++)<br /> cin >> inSeq[i];<br /> _min[n] = INF;<br /> memset(adj, false, sizeof(adj));<br /> memset(color, 0, sizeof(color));<br /> for(int i = n - 1; i >= 0; i--)<br /> _min[i] = min(inSeq[i], _min[i + 1]);<br /> //找到所有无向边<br /> for(int i = 0; i < n; i++) {<br /> for(int j = i + 1; j < n; j++) {<br /> if(inSeq[i] < inSeq[j] && inSeq[i] > _min[j + 1]) {<br /> adj[i][j] = adj[j][i] = true;<br /> }<br /> }<br /> }<br /> //染色<br /> bool ok = true;<br /> for(int i = 0; i < n; i++) {<br /> if(color[i] == 0) {<br /> color[i] = 1;<br /> if(!dfs(i)) {<br /> ok = false;<br /> break;<br /> }<br /> }<br /> }<br /> if(!ok) {<br /> cout << 0 << endl;<br /> continue;<br /> }<br /> //模拟求解<br /> int out = 0; //输出队列的元素个数<br /> path = "";<br /> for(int i = 0; i < n; i++) {<br /> if(color[i] == 1) {<br /> path += "a ";<br /> s1.push(inSeq[i]);<br /> }<br /> else {<br /> path += "c ";<br /> s2.push(inSeq[i]);<br /> }<br /> while((!s1.empty() && s1.top() == out + 1) ||<br /> (!s2.empty() && s2.top() == out + 1)) {<br /> if(s1.top() == out + 1) {<br /> path += "b ";<br /> s1.pop();<br /> }else {<br /> path += "d ";<br /> s2.pop();<br /> }<br /> out++;<br /> }<br /> }<br /> path.erase(path.size() - 1, 1);<br /> cout << path << endl;<br /> }<br /> return 0;<br /> }