Advertisement
srtgguy

Untitled

May 16th, 2021
1,096
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.00 KB | None | 0 0
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4. using namespace std;
  5.  
  6. #define int long long
  7.  
  8. signed main() {
  9.     ios_base::sync_with_stdio(false);
  10.     cin.tie(nullptr);
  11.  
  12.     string s;
  13.     cin >> s;
  14.     int n = s.size();
  15.  
  16.     vector<vector<int>> dp(n, vector<int>(4, 0));
  17.     vector<vector<int>> sum(n, vector<int>(4, 0));
  18.     if (s[0] == 'u') {
  19.         dp[0][0] = 1;
  20.         sum[0][0] = 1;
  21.     }
  22.     for (int i = 1; i < n; ++i) {
  23.         sum[i][0] = sum[i - 1][0];
  24.         sum[i][1] = sum[i - 1][1];
  25.         sum[i][2] = sum[i - 1][2];
  26.         sum[i][3] = sum[i - 1][3];
  27.         if (s[i] == 'u') {
  28.             dp[i][0] = 1;
  29.             ++sum[i][0];
  30.             dp[i][3] = sum[i - 1][2]; //udd + u
  31.             sum[i][3] += dp[i][3];
  32.         } else if (s[i] == 'd') {
  33.             dp[i][1] = sum[i - 1][0]; //u + d
  34.             sum[i][1] += dp[i][1];
  35.             dp[i][2] = sum[i - 1][1];  //ud + d
  36.             sum[i][2] += dp[i][2];
  37.         }
  38.     }
  39.     cout << sum[n - 1][3] << '\n';
  40. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement