1609: [Usaco2008 Feb]Eating Together麻煩的聚餐

Time Limit:?10 Sec??Memory Limit:?64 MB
Submit:?1010??Solved:?606
[Submit][Status]

Description

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

Input

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

Output

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

Sample Input

5

1

3

2

1

1

輸入說明:

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

Sample Output

1

輸出說明:

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

HINT

Source

Silver

題解：一個比較萌的DP，用a[I,j]存儲當修改到第i頭牛時改為j（也可以是保持原狀其實），然后直接掃一遍，接著反向來一遍，注意i=1時最好特判下

?

1 var 2 i,j,k,l,m,n:longint; 3 a:array[0..50000,1..3] of longint; 4 b:array[0..50000] of longint; 5 function min(x,y:longint):longint; 6 begin 7 if x<y then min:=x else min:=y; 8 end; 9 10 begin 11 read(n); 12 for i:=1 to n do read(b[i]); 13 for i:=1 to n do 14 begin 15 if i=1 then 16 begin 17 for j:=1 to 3 do 18 if b[1]=j then a[1,j]:=0 else a[1,j]:=1; 19 end 20 else 21 begin 22 for j:=1 to 3 do 23 begin 24 l:=maxlongint; 25 for k:=1 to j do 26 begin 27 if a[i-1,k]<l then l:=a[i-1,k]; 28 end; 29 if b[i]=j then a[i,j]:=l else a[i,j]:=l+1; 30 end; 31 end; 32 33 end; 34 m:=(min(a[n,3],min(a[n,1],a[n,2]))); 35 for i:=1 to n div 2 do 36 begin 37 l:=b[i]; 38 b[i]:=b[n+1-i]; 39 b[n+1-i]:=l; 40 end; 41 for i:=1 to n do 42 begin 43 if i=1 then 44 begin 45 for j:=1 to 3 do 46 if b[1]=j then a[1,j]:=0 else a[1,j]:=1; 47 end 48 else 49 begin 50 for j:=1 to 3 do 51 begin 52 l:=maxlongint; 53 for k:=1 to j do 54 begin 55 if a[i-1,k]<l then l:=a[i-1,k]; 56 end; 57 if b[i]=j then a[i,j]:=l else a[i,j]:=l+1; 58 end; 59 end; 60 61 end; 62 m:=min(m,min(a[n,3],min(a[n,1],a[n,2]))); 63 writeln(m); 64 end.

?

轉載于:https://www.cnblogs.com/HansBug/p/4163025.html

總結

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

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