因为只有1.2
第i位置如果最后要1，那么i-1位置也必须是1：f[i][1]=f[i-1][i]+g[i]-1
第i位置如果最后要2，那么i-1位置可以是1，也可以使2：f[i][2]=min(f[i-1][1],f[i-1][2])+2-[i];

#include<stdio.h>
int min(int a,int b)
{
  return a<b?a:b;    
} 
int main()
{
  int f[30005][2],g[30005];
  int n;
  scanf("%d",&n);
  for(int i=1;i<=n;i++)
  {
    scanf("%d",&g[i]);        
  }   
  if(g[1]==1)
  {
    f[1][1]=0;
    f[1][2]=1;           
  }
  else
  {
    f[1][1]=1;
    f[1][2]=0;   
  }
  for(int i=2;i<=n;i++)
  {
     
     f[i][1]=f[i-1][1]+g[i]-1;
     f[i][2]=min(f[i-1][1],f[i-1][2])+2-g[i];      
  }
  printf("%d\n",min(f[n][1],f[n][2]));
  return 0;
}

• Re:O(N)复杂度 (8) MONDAY41 2010-05-19 20:22:15