| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
水题,线性DP~~#include<stdio.h>
int min(int a,int b)
{
if (a>b) return b;
return a;
}
int main()
{
int a[30001],f[30001][3],i,j,k,n;
scanf("%d",&n);
for (i=1; i<=n; i++) scanf("%d",&a[i]);
for (i=1; i<=n; i++)
{
f[i][1]=35000;
f[i][2]=35000;
}
if (a[1]==1)
{
f[1][1]=0;
}
else f[1][1]=1;
if (a[1]==2)
{
f[1][2]=0;
}
else f[1][2]=1;
for (i=2; i<=n; i++)
if (a[i]==1)
{
f[i][1]=f[i-1][1];
f[i][2]=min(f[i-1][1],f[i-1][2])+1;
}
else
{
f[i][1]=f[i-1][1]+1;
f[i][2]=min(f[i-1][1],f[i-1][2]);
}
printf("%d",min(f[n][1],f[n][2]));
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator