fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // why am I so weak
  5.  
  6. int n;
  7. int a[2555];
  8. int dp[2555];
  9.  
  10. int main() {
  11. scanf("%d", &n);
  12.  
  13. for (int i = 1; i <= n; i++) {
  14. scanf("%d", &a[i]);
  15. }
  16.  
  17. sort(a + 1, a + n + 1);
  18.  
  19. memset(dp, 63, sizeof(dp));
  20.  
  21. dp[0] = 0;
  22. dp[1] = 1;
  23.  
  24. for (int i = 2; i <= n; i++) {
  25. if (abs(a[i] - a[i - 1]) <= 2) {
  26. dp[i] = min(dp[i], dp[i - 2] + 1);
  27. }
  28.  
  29. dp[i] = min(dp[i], dp[i - 1] + 1);
  30. }
  31.  
  32. printf("%d\n", dp[n]);
  33.  
  34. return 0;
  35. }
Success #stdin #stdout 0s 15264KB
stdin
Standard input is empty
stdout
0