USACO FEB08 Bronze Dining Cows 晚餐队列安排
递推
* 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