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