[動態規劃]USACO Feb08 麻煩的聚餐 egroup 解題報告

【題目描述】
爲了避免餐廳過分擁擠，FJ要求奶牛們分3批就餐。每天晚飯前，奶牛們都會在餐廳前排隊入內，按FJ的設想，所有第3批就餐的奶牛排在隊尾，隊伍的 前端由設定爲第1批就餐的奶牛佔據，中間的位置就歸第2批就餐的奶牛了。由於奶牛們不理解FJ的安排，晚飯前的排隊成了一個大麻煩。

第i頭奶牛有一張標明她用餐批次D_i(1 <= D_i <= 3)的卡片。雖然所有N(1 <= N <= 30,000)頭奶牛排成了很整齊的隊伍，但誰都看得出來，卡片上的號碼是完全雜亂無章的。

在若干次混亂的重新排隊後，FJ找到了一種簡單些的方法：奶牛們不動，他沿着隊伍從頭到尾走一遍，把那些他認爲排錯隊的奶牛卡片上的編號改 掉，最終得到一個他想要的每個組中的奶牛都站在一起的隊列，例如111222333或者333222111。哦，你也發現了，FJ不反對一條前後顛倒的隊 列，那樣他可以讓所有奶牛向後轉，然後按正常順序進入餐廳。

你也曉得，FJ是個很懶的人。他想知道，如果他想達到目的，那麼他最少得改多少頭奶牛卡片上的編號。所有奶牛在FJ改卡片編號的時候，都不會挪位置。

程序名: egroup

輸入格式:

第1行: 1個整數：N

第2..N+1行: 第i+1行是1個整數，爲第i頭奶牛的用餐批次D_i

輸入樣例 (egroup.in):

5

1

3

2

1

1

輸入說明:

隊列中共有5頭奶牛，第1頭以及最後2頭奶牛被設定爲第一批用餐，第2頭奶牛的預設是第三批用餐，第3頭則爲第二批用餐。

輸出格式:

第1行: 輸出1個整數，爲FJ最少要改幾頭奶牛卡片上的編號，才能讓編號變成他設想中的樣子

輸出樣例 (egroup.out):

1

輸出說明:

如果FJ想把當前隊列改成一個不下降序列，他至少要改2頭奶牛的編號，一種可行的方案是：把隊伍中2頭編號不是1的奶牛的編號都改成1。不過，如果FJ選擇把第1頭奶牛的編號改成3就能把奶牛們的隊伍改造成一個合法的不上升序列了。

【分析】

題目上說的已經很清楚了，這就是一個求最長不下降/不上升序列問題。

由於N的最大值是30000，常規O(n^2)的動態規劃解法已經不能再用了，因為會有一組數據超時的。

由於這個序列中只有3個數，我們可以這樣寫：

定義 Q[i]表示：當前以i結尾的最長不下降序列的長度(1<=i<=3)

定義 H[i]表示：當前以i結尾的最長不上升序列的長度(1<=i<=3)

兩個數組都初始化為0。

現在連數組都不用開，直接讀入，邊讀邊算即可。

定義Tmp表示當前讀入的數。

狀態轉移方程：

                        如果Tmp=1:Q[1]=Q[1]+1,H[Tmp]=Max{H[1],H[2],H[3]}+1；

                        如果Tmp=2:Q[2]=Max{Q[1],Q[2]}+1,H[2]=Max{H[2],H[3]}+1；

                       如果Tmp=3:Q[3]=Max{Q[1],Q[2],Q[3]}+1,H[3]=H[3]+1；

最後輸出Min{Max{Q[1],Q[2],Q[3]},Max{H[1],H[2],H[3]}}即可。

【代碼一：O(n^2)的動態規劃】

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
int H[30001];
int S[30001];
int X[30001];
int n;

void init()
{
    scanf("%d\n",&n);
    for (int i=1;i<=n;i++)
        scanf("%d\n",&H[i]);
}

void dp()
{
    //int maxn=0;
    for (int k=1;k<=n;k++)
    {
        //先DP出最長上升序列
        S[1]=1;
        for (int i=2;i<=n;i++)
        {
            S[i]=1;
            for (int j=1;j<=i-1;j++)
            {
                if(H[i]>=H[j] && S[j]+1>S[i])
                    S[i]=S[j]+1;
            }
        }
       
        //再求最長下降序列
        X[n]=1;
        for (int i=n-1;i>=1;i--)
        {
            X[i]=1;
            for (int j=i+1;j<=n;j++)
            {
                if(H[i]>=H[j] && X[j]+1>X[i])
                    X[i]=X[j]+1;
            }
        }
    }
   
   
    int Maxa=0;
    int Maxb=0;
    for (int i=1;i<=n;i++)
    {
        if(S[i]>Maxa)
            Maxa=S[i];
        if(X[i]>Maxb)
            Maxb=X[i];
    }
    int Min=n-Maxa;
   
    if(Min>(n-Maxb))
        Min=n-Maxb;
   
    cout<<Min<<endl;
}

int main()
{
    freopen("egroup.in","r",stdin);
    freopen("egroup.out","w",stdout);
    init();
    dp();
    //printf("%d\n",n-dp());
    return 0;
}

【代碼二：O(n)的動態規劃】

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

int Max2(int a,int b)
{
    if(b>a)
        a=b;
    return a;
}

int Max3(int a,int b,int c)
{
    if(b>a)
        a=b;
    if(c>a)
        a=c;
    return a;
}

void work()
{
    int Q[4]={0,0,0,0};
    int H[4]={0,0,0,0};
    int N;
    int Tmp=0;

    scanf("%d\n",&N);
   
    for (int i=1;i<=N;i++)
    {
        cin>>Tmp;
        if(Tmp==1)
        {
            Q[1]++;
            H[1]=Max3(H[1],H[2],H[3])+1;
            continue;
        }
        if(Tmp==2)
        {
            Q[2]=Max2(Q[1],Q[2])+1;
            H[2]=Max2(H[2],H[3])+1;
            continue;
        }
        Q[3]=Max3(Q[1],Q[2],Q[3])+1;
        H[3]++;
    }
    int MAX1=Max3(H[1],H[2],H[3]);
    int MAX2=Max3(Q[1],Q[2],Q[3]);
    MAX1=N-Max2(MAX1,MAX2);
    printf("%d\n",MAX1);
}

int main()
{
    freopen("egroup.in","r",stdin);
    freopen("egroup.out","w",stdout);
    work();
    return 0;
}