題目描述

為了避免餐廳過分擁擠，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改卡片編號的時候，都不會挪位置。

輸入格式

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

輸出格式

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

---

思路1：先正著求出最長不下降子序列的長度len1，再反著求出最長不上升子序列的長度len2，那么：

\[ ans=min(n-len1,n-len2) \]

其時間復雜度可以做到

\[ O(N*logN) \]

思路2：這題只有3個批次，我們應該好好利用這點來求出最長不下降子序列和最長不上升子序列。

設dp(i,j,0)表示第i頭奶牛的批次為j時，最長不下降子序列的長度；dp(i,j,1)第i頭奶牛的批次為j時，最長不上升子序列的長度。容易得出：

\[ dp(i,1,0)=dp(i-1,1,0)+[a[i]=1]\\ dp(i,1,1)=min(dp(i-1,1,1),dp(i-1,2,1),dp(i-1,3,1))+[a[i]=1]\\ dp(i,2,0)=min(dp(i-1,1,0),dp(i-1,2,0))+[a[i]=2]\\ dp(i,2,1)=min(dp(i-1,2,1),dp(i-1,3,1))+[a[i]=2]\\ dp(i,3,0)=min(dp(i-1,1,0),dp(i-1,2,0),dp(i-1,3,0))+[a[i]=3]\\ dp(i,3,1)=dp(i-1,3,1)+[a[i]=3] \]

于是我們枚舉每個i即可，時間復雜度為

\[ O(N) \]

#include<iostream> #include<cstring> #include<cstdio> #define maxn 30001 using namespace std;inline int read(){register int x(0),f(1); register char c(getchar());while(c<'0'||'9'<c){ if(c=='-') f=-1; c=getchar(); }while('0'<=c&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();return x*f; }int a[maxn],n,dp[maxn][4][2],ans=0x3f3f3f3f; int main(){n=read();for(register int i=1;i<=n;i++) a[i]=read();for(register int i=1;i<=n;i++){dp[i][1][0]=dp[i-1][1][0]+(a[i]!=1);dp[i][2][0]=min(dp[i-1][1][0],dp[i-1][2][0])+(a[i]!=2);dp[i][3][0]=min(dp[i-1][1][0],min(dp[i-1][2][0],dp[i-1][3][0]))+(a[i]!=3);dp[i][1][1]=min(dp[i-1][1][1],min(dp[i-1][2][1],dp[i-1][3][1]))+(a[i]!=1);dp[i][2][1]=min(dp[i-1][2][1],dp[i-1][3][1])+(a[i]!=2);dp[i][3][1]=dp[i-1][3][1]+(a[i]!=3);}ans=min(min(dp[n][1][0],min(dp[n][2][0],dp[n][3][0])),min(dp[n][1][1],min(dp[n][2][1],dp[n][3][1])));printf("%d\n",ans);return 0; }

轉載于:https://www.cnblogs.com/akura/p/10846709.html

總結

以上是生活随笔為你收集整理的[Usaco2008 Feb]Eating Together麻烦的聚餐的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。