Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

水题,线性DP~~

Posted by lijiaming12340 at 2013-10-28 16:52:52 on Problem 3671
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator