fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = 2e5 + 1;
  5. int n, c[N], Next[N], last[N], dp[N];
  6.  
  7. int calc(int at) {
  8. 	if (at == n - 1)
  9. 		return 0;
  10. 	int &res = dp[at];
  11. 	if (res != -1)
  12. 		return res;
  13. 	res = calc(at + 1) + 1;
  14. 	if (Next[at] != -1)
  15. 		res = min(res, calc(Next[at]) + 1);
  16. 	return res;
  17. }
  18.  
  19. int main(int argc, char **argv) {
  20. 	int t;
  21. 	scanf("%d", &t);
  22. 	while (t-- != 0) {
  23. 		scanf("%d", &n);
  24. 		for (int i = 0; i < n; ++i)
  25. 			scanf("%d", &c[i]);
  26. 		memset(dp, -1, sizeof dp);
  27. 		memset(last, -1, sizeof last);
  28. 		for (int i = n - 1; i >= 0; --i) {
  29. 			Next[i] = last[c[i]];
  30. 			last[c[i]] = i;
  31. 		}
  32. 		printf("%d\n", calc(0));
  33. 	}
  34. 	return 0;
  35. }
Time limit exceeded #stdin #stdout 5s 8388607KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/UnBst5
language:
C++ (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!