总时间限制: 

10000ms

 

单个测试点时间限制: 

1000ms

 

内存限制: 

65536kB

描述

LGTB 有一个长度为 N 的序列。当序列中存在相邻的两个数的和为偶数的话，LGTB 就能把它们删掉。

LGTB 想让序列尽量短，请问能将序列缩短到几个数？

输入

第一行包含一个数 N 代表序列初始长度
接下来一行包含 N 个数 a1, a2, ..., aN，代表序列

输出

输出包含一个数代表操作后序列最短长度

样例输入

10
1 3 3 4 2 4 1 3 7 1

样例输出

2

提示

对于 50% 的数据，1 ≤ N ≤ 1000
对于 100% 的数据，1 ≤ N ≤ 1e5
, 0 ≤ ai ≤ 1e9

【思路】

一开始dp死活做不出来...

栈 边读边处理....

不太明白为什么处理顺序对答案没影响...

【code】

//05:LGTB 与偶数
#include<iostream>
#include<cstdio>
using namespace std;
int n,top,sz[100009],stack[100009];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&sz[i]);
        if(!top)stack[++top]=sz[i];
        else
        if(((stack[top]+sz[i])&1)==0)
        top--;
        else
        stack[++top]=sz[i];
    }
    printf("%d\n",top);
    return 0;
}

 

05:LGTB 与偶数