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

Time Limit:?10 Sec??Memory Limit:?64 MB
Submit:?1646??Solved:?1005
[Submit][Status][Discuss]

Description

為了避免餐廳過分擁擠，FJ要求奶牛們分3批就餐。每天晚飯前，奶牛們都會在餐廳前排隊(duì)入內(nèi)，按FJ的設(shè)想所有第3批就餐的奶牛排在隊(duì)尾，隊(duì)伍的前端由設(shè)定為第1批就餐的奶牛占據(jù)，中間的位置就歸第2批就餐的奶牛了。由于奶牛們不理解FJ的安排，晚飯前的排隊(duì)成了一個(gè)大麻煩。 第i頭奶牛有一張標(biāo)明她用餐批次D_i(1 <= D_i <= 3)的卡片。雖然所有N(1 <= N <= 30,000)頭奶牛排成了很整齊的隊(duì)伍但誰都看得出來，卡片上的號碼是完全雜亂無章的。 在若干次混亂的重新排隊(duì)后，FJ找到了一種簡單些的方法：奶牛們不動，他沿著隊(duì)伍從頭到尾走一遍把那些他認(rèn)為排錯(cuò)隊(duì)的奶牛卡片上的編號改掉，最終得到一個(gè)他想要的每個(gè)組中的奶牛都站在一起的隊(duì)列，例如111222333或者333222111。哦，你也發(fā)現(xiàn)了，FJ不反對一條前后顛倒的隊(duì)列，那樣他可以讓所有奶牛向后轉(zhuǎn)，然后按正常順序進(jìn)入餐廳。 你也曉得，FJ是個(gè)很懶的人。他想知道，如果他想達(dá)到目的，那么他最少得改多少頭奶牛卡片上的編號。所有奶牛在FJ改卡片編號的時(shí)候，都不會挪位置。

Input

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

Output

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

Sample Input

5
1
3
2
1
1
輸入說明:

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

Sample Output

1

輸出說明:

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

HINT

Source

Silver

?

Analysis

這是一道遞推qwq

（然而我喪心病狂地去求最長升/降序，英勇送TLE）

定義狀態(tài)為 DP[ 前 i 個(gè)數(shù) ][ 以 j 結(jié)尾 ] = 最小修改次數(shù)

那么我們可以根據(jù)這個(gè)狀態(tài)直接AC了..

代碼中PD的意思就是逆過來DP嗯（嚴(yán)格來說不算DP）

?

Code

1 #include<cstdio> 2 #include<iostream> 3 #define maxn 1000000 4 //using namespace std; 5 6 int min(int a,int b){return a<b?a:b;} 7 int min(int a,int b,int c){return min(min(a,b),c);} 8 9 int arr[maxn],DP[maxn][4],PD[maxn][4],n; 10 11 int main(){ 12 scanf("%d",&n); 13 14 for(int i = 1;i <= n;i++){ 15 scanf("%d",&arr[i]); 16 17 switch(arr[i]){ 18 case 1: 19 DP[i][1] = DP[i-1][1]; 20 DP[i][2] = min(DP[i-1][1],DP[i-1][2]+1); 21 DP[i][3] = min(DP[i-1][1],DP[i-1][2]+1,DP[i-1][3]+1); 22 break; 23 case 2: 24 DP[i][1] = DP[i-1][1]+1; 25 DP[i][2] = min(DP[i-1][1],DP[i-1][2]); 26 DP[i][3] = min(DP[i-1][1],DP[i-1][2],DP[i-1][3]+1); 27 break; 28 case 3: 29 DP[i][1] = DP[i-1][1]+1; 30 DP[i][2] = min(DP[i-1][1]+1,DP[i-1][2]+1); 31 DP[i][3] = min(DP[i-1][1],DP[i-1][2],DP[i-1][3]); 32 break; 33 } 34 } 35 36 for(int i = n;i >= 1;i--){ 37 switch(arr[i]){ 38 case 1: 39 PD[i][1] = PD[i+1][1]; 40 PD[i][2] = min(PD[i+1][1],PD[i+1][2]+1); 41 PD[i][3] = min(PD[i+1][1],PD[i+1][2]+1,PD[i+1][3]+1); 42 break; 43 case 2: 44 PD[i][1] = PD[i+1][1]+1; 45 PD[i][2] = min(PD[i+1][1],PD[i+1][2]); 46 PD[i][3] = min(PD[i+1][1],PD[i+1][2],PD[i+1][3]+1); 47 break; 48 case 3: 49 PD[i][1] = PD[i+1][1]+1; 50 PD[i][2] = min(PD[i+1][1]+1,PD[i+1][2]+1); 51 PD[i][3] = min(PD[i+1][1],PD[i+1][2],PD[i+1][3]); 52 break; 53 } 54 } 55 56 int ans = min(min(PD[1][1],PD[1][2],PD[1][3]),min(DP[n][1],DP[n][2],DP[n][3])); 57 58 printf("%d",ans); 59 60 return 0; 61 } 我被水題欺負(fù)嚶嚶嚶

轉(zhuǎn)載于:https://www.cnblogs.com/Chorolop/p/7460054.html

總結(jié)

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

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。