USACO FEB08 Bronze Dining Cows 晚餐隊列安排
本文正體字版由OpenCC轉換
遞推
* F[i] 爲以第i個數爲分界點(i屬於上段)，使上下兩段分別全爲1和全爲2，所要更改的最少的卡片的數目。
遞推方程
* F[i]=
o F[i-1]-1 (第i個數爲1)
o F[i-1]+1 (第i個數爲2)
邊界條件
* F[0]=數列中1的個數（把1全部改成2）
目標結果
* Min{ F[i] } (0<=i<=N)
/*
ID: cmykrgb1
PROG: diningb
LANG: C++
*/
#include <iostream>
#define MAX 30001
using namespace std;
int C[MAX],F[MAX];
int N,cnt,Ans;
int main()
{
int i;
freopen("diningb.in","r",stdin);
freopen("diningb.out","w",stdout);
cin >> N;
for (i=1;i<=N;i++)
{
cin >> C[i];
if (C[i]==1)
cnt++;
}
Ans=F[0]=cnt;
for (i=1;i<=N;i++)
{
F[i]=F[i-1];
if (C[i]==1)
F[i]--;
else
F[i]++;
if (F[i]<Ans)
Ans=F[i];
}
cout << Ans << endl;
return 0;
}
上次修改時間 2017-02-03