（たぶん）普通の解き方

POJ3671 Dining Cows(1)

http://acm.pku.edu.cn/JudgeOnline/problem?id=3671
左側に1、右側に2を固めるということは、数字の列に1箇所仕切りを入れて数字の列を左右に分割してしまえば良いでしょう。前回の例で考えると、

 2 1 1 1 2 2 1

は、4つ目と5つ目の間に仕切りを入れ

 2 1 1 1|2 2 1

左側では2を1に、右側では1を2に反転すると

 1 1 1 1 2 2 2

のように完成します。つまり、数字の列のどの点で分割すると最適解となるのかを考えれば良いということになります。
どこで分割するのが最適かを考えるのは、それほど難しいことではありません。左から順に仕切りの位置を移動して反転コストを計算しながら、反転コストが最小になる部分を記憶するだけで良いのです。

まず、仕切りの位置を一番左にします。

|2 1 1 1 2 2 1

仕切りが一番左にくると、反転後の状態は

 2 2 2 2 2 2 2

のようにすべてが2になります。この場合、1が4箇所あったので反転コストは4になり、この値が基準となります。

次に、仕切りの位置を右にずらします。

 2|1 1 1 2 2 1

この場合、反転後の状態は

 1 2 2 2 2 2 2

になります。最初の数字は2ですから、この数を反転させなければならず、反転コストは1増加することになり、4+1=5となってしまいます。

さらに仕切りを右にずらします。

 2 1|1 1 2 2 1

この場合、反転後の状態は

 1 1 2 2 2 2 2

のようになります。2番目の数字は元々1なので反転する必要がなくなり、反転コストが1減少、すなわち5-1=4で、基準値に戻ります。

更に右にずらした場合、同様に考えると反転コストは1減少して3になり、最小値を更新します。この手順で左から右に走査すれば最適解を求めることが出来るようになります。

以下、サンプルコード

#include<stdio.h>

int buf[30000];

int main()
{
  int i,n;
  int c1=0; /* 反転コスト */
  int min;
  
  scanf("%d",&n);
  for(i=0;i<n;++i)
  {
    scanf("%d",&buf[i]);
    if(buf[i]==1) ++c1; /* "1"の数が基準の反転コスト */
  }

  min=c1;
  
  for(i=0;i<n;++i)
  {
    if(buf[i]==1) --c1;
    else if(buf[i]==2) ++c1;
  
    if(c1<min) min=c1;
  }
  
  printf("%d\n", min);

  return 0;
}