e588: 12385 - Interesting Sequences
Tags :
Accepted rate : 4人/4人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2019-10-30 22:35

Content

對於整數序列<x1, x2, ..., xn>,的連續子序列<xi, xi + 1, ..., xj>,其中i < j ≤ n。
如果第一個元素和最後一個元素相等(即xi = xj),我們稱為稱為"interesting"。
兩個"interesting"的子序列S1 = <xi, xi + 1, ..., xj>和S2 = <xa, xa + 1, ..., xb>,其中a ≥ j 或 i ≥ b稱為"conflictfree"。
題目將會給定已知大小的序列,請你找出最大數量的"interesting"序列,並且彼此"conflictfree"。

Input

輸入的第一行包含一個整數 T (T ≤ 100),代表測資數量。
每組測資的第一行為一個整數N (1 ≤ N ≤ 100000),代表此序列的大小。
下一行包含N個正整數,每個正整數在1到100000之間。

Output

對於每組測資,輸出最大數量的"interesting"序列,並且彼此"conflictfree"。

Sample Input
3
6
1 2 1 3 1 2
4
2 4 2 4
9
10 2 2 10 3 4 5 4 3
Sample Output
2
1
2
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (50%): 1.0s , <1M
公開 測資點#1 (50%): 1.0s , <10M
Hint :
Tags:
出處:
UVA [管理者:
ig99lp33lp33 (원스)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」