# Kattis - evenup

[題目連結](https://open.kattis.com/problems/evenup)

## 題目敘述

The Even Up Solitaire can be played with a stack of cards each having a numerical value from 1 to 100. The cards are laid out from left to right in a row. At every step, the player is allowed to remove two adjacent cards if the sum of their values is even. The gap is then “closed” by shifting the cards to the right of the gap. The order of the remaining cards is not changed. The game stops when all cards are removed or when no more cards can be removed. The player wins when all cards are removed. If this is not possible, the player should try to minimize the number of cards remaining.

You are given the initial list of cards, in left-to-right order. Determine the minimum number of cards that remain if the player moves optimally.

:::success
Even Up Solitaire 是個卡片遊戲，每張卡片各有一個 $1$ 到 $100$ 的數字。卡片會從左到右擺成一個橫排，每一步玩家可以任選兩張相鄰且數字相加為偶數的牌，將它們一起丟掉。之後會將左邊的牌維持原順序往右遞補，填滿空出來的位置。移動後所有的牌都會保持原順序。遊戲會在所有牌都被丟掉，或沒有任何牌可以被移除時結束。如果所有牌都被丟掉，則玩家獲勝。如果這不可能達成，則玩家要盡力最小化剩下的牌數。

將牌由左到右依序告訴你，你必須算出在最佳策略之下，最少會剩多少張牌。
:::

## 輸入格式

The input consists of one case. The first line contains an integer $n$ ($1\le n\le 100000$) giving the number of cards to follow. The second line contains $n$ integers indicating the card values from left to right. Each card value is in the range $1$ to $100$.

:::success
輸入僅包含一組測試資料。第一行有一整數 $n$（$1\le n\le 100000$）表示有多少張牌，第二行會給你 $n$ 個整數，依序是由左到右每張牌的數字。牌的數字範圍介於 $1$ 到 $100$ 之間。
:::

## 輸出格式

Print the minimum number of cards that remain if the player moves optimally.

:::success
輸出在最佳策略下，剩下無法丟掉的最小牌數。
:::

## Sample Input

10
1 2 3 4 5 6 7 8 9 10

## Sample Output

10

## Sample Input

10
1 3 3 4 2 4 1 3 7 1

## Sample Output

2

{%hackmd @sa072686/__style %}

###### tags: `翻譯`, `Kattis`