[UVA] 12385 - Interesting Sequences
I - Interesting Sequences
For a sequence of integer numbers <x1,x2,…,xn>, a contiguous subsequence <xi,xi+1,…,xj> where i<j≤n, is called "interesting" if its first and last elements are equal (i.e., xi=xj). Two interesting subsequences S1=<xi,xi+1,…,xj> and S2=<xa,xa+1,…,xb> are called conflict-free if either a≥j or i≥b.
For a given sequence of known size, find the maximum number of interesting subsequences which are pairwise conflict-free.
Input
The first line of input contains an integer T≤100 denoting the number of test-cases. Each test-case begins with an integer 1≤N≤100,000, on a separate line, denoting the size of the sequence. The following line contains N positive integers each between 1 and 100,000 (inclusive).
Output
For each test-case, output on a single line the maximum number of pairwise conflict-free interesting subsequences.
|
Sample Input |
Sample Output |
|
3 6 1 2 1 3 1 2 4 2 4 2 4 9 10 2 2 10 3 4 5 4 3 |
2 1 2 |
做法 : Greedy
題目意思 : 找最多不重疊的線段
例如 10 2 2 10 3 4 5 4 3
[10 2 2 10] 3 [4 5 4] 3 因此有兩個線段
#include <stdio.h>
#include <string.h>
int main() {
int T, N, i, x;
int set[100001];
scanf("%d", &T);
while(T--) {
scanf("%d", &N);
memset(set, -1, sizeof(set));
int Ans = 0, last = -1;
for(i = 0; i < N; i++) {
scanf("%d", &x);
if(set[x] >= last && set[x] != 0xffffffff) {
Ans++, last = i;
}
set[x] = i;
}
printf("%d\n", Ans);
}
return 0;
}