题目来源：https://oj.hfuuacm.xyz/problem/show/1177

Description

MDH已经是HFUU的国际级的明星选手，但是XYQ仍然表示不服，于是XYQ对明星选手发起了最后的提问。问题如下：先给你一个含有N个整数的数组数组中的每一个元素只为1或者0而N的大小为1~100你可以删除一些元素（也可以选择不删除），使剩下的数组中，没有一个元素0在1后面出现。并且要使剩下的元素的数量最多，请输出剩下元素的数量。

Input

第一行，一个整数N

接下来一行，含有N个整数，每一个整数为0或者1

Output

一个整数，代表可以保留下的数组的最大的元素数量

Sample Input

 

6 0 1 0 0 1 0

6 0 1 0 0 1 0

 

Sample Output

4

Hint

MDH太强了

Source

MDH

Tags

思路：前缀记0，后缀记1；

参考代码：

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 110
struct node
{
    int q,h;
} ans[N];
int sum[N];
bool cmp(node a,node b)
{
    return (a.h+a.q)>(b.h+b.q);
}
int main()
{
    int n;
    cin>>n;
    for(int i=1; i<=n; i++)
        cin>>sum[i];
    memset(ans,0,sizeof(ans));
    if(!sum[1])
        ans[1].q=1;
    if(sum[n])
        ans[n].h=1;
    for(int i=2; i<=n; i++)
        ans[i].q = (sum[i]==0 ? ans[i-1].q+1 : ans[i-1].q);
    for(int i=n-1; i>=1; i--)
        ans[i].h = (sum[i]==1 ? ans[i+1].h+1 : ans[i+1].h);
    sort(ans+1,ans+n+1,cmp);
    cout<<ans[1].q+ans[1].h<<endl;
    return 0;
}