Advertisement
Guest User

Untitled

a guest
Mar 29th, 2020
78
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.96 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cmath>
  4. #include <vector>
  5. #include <string>
  6. #include <cstring>
  7. #include <cstdlib>
  8. #include <iomanip>
  9. #include <map>
  10. #include <set>
  11. #include <unordered_map>
  12. #include <unordered_set>
  13.  
  14. using namespace std;
  15.  
  16.  
  17. long long dp[2][200005];
  18.  
  19. signed main() {
  20. ios_base::sync_with_stdio(false);
  21. cin.tie(nullptr);
  22. cout.tie(nullptr);
  23. freopen("hike.in", "r", stdin);
  24. freopen("hike.out", "w", stdout);
  25. string s;
  26. cin >> s;
  27. dp[0][0] = 0;
  28. dp[1][0] = 1;
  29. for (int i = 0; i < s.length(); i++) {
  30. if (s[i] == 'L') {
  31. dp[0][i + 1] = min(dp[0][i] + 1, dp[1][i] + 1);
  32. dp[1][i + 1] = min(dp[0][i] + 2, dp[1][i]);
  33. }
  34. else if (s[i] == 'R') {
  35. dp[0][i + 1] = min(dp[0][i], dp[1][i] + 2);
  36. dp[1][i + 1] = min(dp[0][i] + 1, dp[1][i] + 1);
  37. }
  38. else {
  39. dp[0][i + 1] = min(dp[0][i] + 1, dp[1][i] + 2);
  40. dp[1][i + 1] = min(dp[0][i] + 2, dp[1][i] + 1);
  41. }
  42. }
  43. cout << dp[1][s.length()];
  44. return 0;
  45. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement