這道題的錯誤做法很多,但是實際在考場上，大多數人拿到了30分。錯誤做法卻能得滿分的也很多,正確的算法是基於二分圖的算法。注意，不是二分圖匹配！

分析條件，我們把問題抽象爲數學模型。設輸入序列爲S，考慮S[i],S[j]兩個元素不能進入同一個棧的條件.注意,這裏所說的"S[i],S[j]兩個元素不能進入同一個棧",不是說僅僅不能同時在一個棧中,而是自始至終不能進入一個棧,即如果有解,那麼S[i],S[j]一定進入過的棧不同.

結論P: S[i],S[j]兩個元素不能進入同一個棧 <=> 存在k,滿足i<j<k,使得S[k]<S[i]<S[j]. 證明略過,請參考sqybi.嘗試後可以發現結論P是正確的.

把每個元素按照輸入序列中的順序編號,看作一個圖中的每個頂點.這時,我們對所有的(i,j)滿足i<j,判斷是否滿足結論P,即S[i],S[j]兩個元素能否進入同一個棧.如果滿足P,則在i,j之間連接一條邊.

我們對圖染色,由於只有兩個棧,我們得到的圖必須是二分圖才能滿足條件.由於要求字典序最小,即儘量要進入棧1,我們按編號遞增的順序從每個未染色的頂點開始染色,相鄰的頂點染上不同的色,如果發生衝突,則是無解的.否則我們可以得到每個頂點顏色,即應該進入的棧.

接下來就是輸出序列了,知道了每個元素的決策,直接模擬了.

在判斷數對(i,j)是否滿足P時,枚舉檢查是否存在k的時間複雜度是O(n),則總的時間複雜度是O(n^3),對於n=1000是太大了.這原因在於過多得枚舉了k,我們可以用動態規劃把枚舉k變爲O(1)的算法.

設F[i]爲Min{S[i],S[i+1],S[i+2]..S[n-1],S[n]},狀態轉移方程爲F[i]=Min{ S[i] , F[i+1] }.邊界爲F[N+1]=極大的值.

判斷數對(i,j)是否滿足P,只需判斷(S[i]<S[j] 並且 F[j+1]<S[i])即可.時間複雜度爲O(n^2).

參考資料:sqybi的題解

/* 
 * Problem: NOIP2008 twostack
 * Author: Guo Jiabao
 * Time: 2008.12.9 21:22:52
 * State: Solved 
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

using namespace std;

const int MAXN=1002;
const int INF=0x7FFFFFFF;

class tStack
{
    private:
        int top;
        int S[MAXN];
    public:
        tStack() : top(0) {}
        void ins(int k)
        {
            S[++top]=k;
        }
        int tp()
        {
            return S[top];
        }
        void pop()
        {
            top--;
        }
};

int S[MAXN],F[MAXN],bel[MAXN];
bool adjm[MAXN][MAXN];
int N,top1,top2;
tStack T[3];

void init()
{
    int i;
    freopen("twostack.in","r",stdin);
    freopen("twostack.out","w",stdout);
    scanf("%d",&N);
    for (i=1;i<=N;i++)
    {
        scanf("%d",&S[i]);
    }
}

void noanswer()
{
    printf("0");
    exit(0);
}

void color(int i,int c)
{
    bel[i]=c;
    int j;
    for (j=1;j<=N;j++)
    {
        if (adjm[i][j])
        {
            if (bel[j]==c) //conflict : not a bipartite graph
            {
                noanswer();
            }
            if (!bel[j])
            {
                color(j,3-c); // color the opposite color 1<->2
            }
        }
    }
}

void dye()
{
    int i,j;
    F[N+1]=INF;
    for (i=N;i>=1;i--)
    {
        F[i]=S[i];
        if (F[i+1]<F[i])
            F[i]=F[i+1];
    }
    for (i=1;i<=N-1;i++)
    {
        for (j=i+1;j<=N;j++)
        {
            if (S[i]<S[j] && F[j+1]<S[i])
            {
                adjm[i][j]=adjm[j][i]=true;
            }
        }
    }
    for (i=1;i<=N;i++)
    {
        if (!bel[i])
        {
            color(i,1);
        }
    }
}

void solve()
{
    int i,should=1,s;
    for (i=1;i<=N;i++)
    {
        s=bel[i];
        if (s==1)
        {
            T[1].ins(S[i]);
            printf("a ");
        }
        else
        {
            T[2].ins(S[i]);
            printf("c ");
        }
        while (T[1].tp()==should || T[2].tp()==should)
        {
            if (T[1].tp()==should)
            {
                T[1].pop();
                printf("b");
                if (should!=N)
                    printf(" ");
                should++;
            }
            else
            {
                T[2].pop();
                printf("d");
                if (should!=N)
                    printf(" ");
                should++;
            }
        }
    }
}

int main()
{
    init();
    dye();
    solve();
    return 0;
}