1316 . 晶片設計 Chips
TopCoder
Description
現在有許多個晶片排成一列，其中兩兩希望連成一對(但一對晶片不一定相鄰)，如下圖所示。
然而一個小小(其實不小)的問題是，由於空間關係，晶片間的連線最多只能列上方一條，列下方一條
也就是同一個鉛直位置最多只有兩條連線經過。
試問給定一列晶片的配對條件，在符合上述連線方式的情況下，最多可以連接幾對晶片？
Input Format
第一行為一個整數n，代表總共有幾對晶片。
接下來有2n個整數，之間用空白或換行分隔，代表由左至右晶片的相連關係，要相連的兩個晶片號碼會相同。
這些整數恰好是1~n。
晶片對數n<=4000
Output Format
一個整數p，代表最多可以連接幾對晶片。
Sample Input 1
6
1 2 3 1 4 5 5 3 2 6 4 6
1 2 3 1 4 5 5 3 2 6 4 6
Sample Output 1
4
Hints
可以連1, 4, 5, 6等四個晶片
Problem Source
原TIOJ1316 / TIOJ IOI Warmup III, 2008. Problemsetter: tmt514, kelvin
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 5 |
| 2 | 1 | 5 |
| 3 | 2 | 5 |
| 4 | 3 | 5 |
| 5 | 4 | 5 |
| 6 | 5 | 5 |
| 7 | 6 | 5 |
| 8 | 7 | 5 |
| 9 | 8 | 5 |
| 10 | 9 | 5 |
| 11 | 10 | 5 |
| 12 | 11 | 5 |
| 13 | 12 | 5 |
| 14 | 13 | 5 |
| 15 | 14 | 5 |
| 16 | 15 | 5 |
| 17 | 16 | 5 |
| 18 | 17 | 15 |