fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MAX_N = 2e5 + 5;
  5.  
  6. void solve() {
  7. int h, n;
  8. cin >> h >> n;
  9. vector<int> a(n + 1, 0);
  10. vector<int> dp(n + 1, MAX_N);
  11. for (int i = 0; i < n; i++) cin >> a[i];
  12. dp[0] = 0;
  13. for (int i = 0; i <= n; i++) {
  14. if (i + 1 <= n) {
  15. dp[i + 1] = min(dp[i + 1], dp[i] + 1);
  16. }
  17. if (i + 2 <= n && a[i + 1] - 1 == a[i + 2]) {
  18. dp[i + 2] = min(dp[i + 2], dp[i] + 1);
  19. if (i + 2 == n) dp[i + 2] = dp[i];
  20. }
  21. }
  22. cout << "dp: ";
  23. for (int i = 0; i <= n; i++) cout << dp[i] << " "; cout << endl;
  24. cout << dp[n] << endl;
  25. }
  26.  
  27. int main() {
  28. int t;
  29. cin >> t;
  30. while (t--) solve();
  31. }
Success #stdin #stdout 0s 5280KB
stdin
4
3 2
3 1
8 6
8 7 6 5 3 2
9 6
9 8 5 4 3 1
1 1
1
stdout
dp: 0 1 0 
0
dp: 0 1 1 2 3 3 4 
4
dp: 0 1 2 2 3 4 3 
3
dp: 0 1 
1