[動態規劃]USACO Feb08 Bronze : Dining Cows 晚餐隊列安排(diningb) 解題報告

【題目描述】

爲了避免餐廳過分擁擠，FJ要求奶牛們分2批就餐。每天晚飯前，奶牛們都

會在餐廳前排隊入內，按FJ的設想，所有第2批就餐的奶牛排在隊尾，隊伍的前半部分則由設定爲第1批就餐的奶牛佔據。由於奶牛們不理解FJ的安排，晚飯前的排隊成了一個大麻煩。

第i頭奶牛有一張標明她用餐批次D_i(1 <= D_i <= 2)的卡片。雖然所有N

(1 <= N <= 30,000)頭奶牛排成了很整齊的隊伍，但誰都看得出來，卡片上的號碼是完全雜亂無章的。

在若干次混亂的重新排隊後，FJ找到了一種簡單些的方法：奶牛們不動，他沿着隊伍從頭到尾走一遍，把那些他認爲排錯隊的奶牛卡片上的編號改掉，最終

得到一個他想要的每個組中的奶牛都站在一起的隊列，例如112222或111122。有的時候，FJ會把整個隊列弄得只有1組奶牛（比方說，1111或222）。

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

輸入：

第1行: 1個整數：N

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

輸出：

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

輸入樣例：

7

2

1

1

1

2

2

1

輸出樣例：

2

【分析】
這是一道線性的動態規劃題目，也是枚舉斷點的那一種DP類型。

首先預處理一下：
  one[i]表示前i個奶牛中卡片為1的個數，
  two[i]表示前i個奶牛中卡片為2的個數。
  S1表示卡片1的總個數，
  S2表示卡片2的總個數。

然後在0-N之間枚舉斷點k，即編號為1～k奶牛的卡片都是1，編號為k+1～N奶牛的卡片都是2，算出不一樣的卡片數即可。

最優的解就是 Min{   two[k]+S1-one[k]  }  (0<=k<=N)


【我的代碼】
#include <iostream>
#include <cstdio>
using namespace std;

class POSITION
{
public:
    int one;
    int two;
}P[30001];
int N;
int S1=0,S2=0;

void init()
{
    scanf("%d\n",&N);
    int Tmp;
    for (int i=1;i<=N;i++)
    {
        scanf("%d\n",&Tmp);
        if(Tmp==1)
            S1++;
        else
            S2++;
        P[i].one=S1;
        P[i].two=S2;
    }
    return;
}

void dp()
{
    int S=0x7fffffff;
    int Tmp;
    for (int i=0;i<=N;i++)
    {
        Tmp=P[i].two+S1-P[i].one;
        if(Tmp<S)
            S=Tmp;
    }
    printf("%d\n",S);
}

int main()
{
    freopen("diningb.in","r",stdin);
    freopen("diningb.out","w",stdout);
    init();
    dp();
    return 0;
}