poj 3671 Dining Cows (Dp)

/*
一开始并没有想出On的正解
后来发现题解的思路也是十分的巧妙的
还是没能把握住题目的 只有1 2这两个数的条件
dp还带练练啊 ... 
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 100010
using namespace std;
int n,a[maxn],Q[maxn],H[maxn],ans=0x7fffffff;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
      scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
      if(a[i]==2)Q[i]=Q[i-1]+1;
      else Q[i]=Q[i-1];
    for(int i=n;i>=1;i--)
      if(a[i]==1)H[i]=H[i+1]+1;
      else H[i]=H[i+1];
    for(int i=1;i<=n;i++)
      ans=min(ans,Q[i]+H[i]-1);
    printf("%d
",ans);
    return 0;
}