a562. CPE：Interesting Sequences (UVa 12385)

題目描述

序列的一段連續子序列 xi,…,xj，若 i<j 且 xi=xj，稱為有趣子序列。兩段 [i,j] 與 [a,b] 若 a≥j 或 i≥b，便沒有衝突；也就是可以共用一個端點，但內部不能重疊。求最多能選出幾段兩兩不衝突的有趣子序列。

輸入格式

第一行 T（T ≤ 100）。每筆先給 N（1 ≤ N ≤ 100000），下一行給 N 個正整數，每個介於 1 與 100000。

輸出格式

每筆輸出一行最多可選取的段數。

來源：UVa 12385 — Interesting Sequences。本敘述依原題規格重新撰寫。