Josif_tepe

Untitled

Oct 15th, 2025
207
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.80 KB | None | 0 0
  1. #include <iostream>
  2. #include <set>
  3. #include <queue>
  4. #include <vector>
  5. #include <cstring>
  6. using namespace std;
  7. const int maxn = 1e5 + 10;
  8. const int INF = 2e9;
  9. string s;
  10. int n;
  11. int dp[maxn];
  12.  
  13. int rec(int at) {
  14.     if(at >= n) {
  15.         return 1;
  16.     }
  17.    
  18.     if(dp[at] != -1) {
  19.         return dp[at];
  20.     }
  21.    
  22.     int res = 0;
  23.    
  24.     if(s[at] != '0') {
  25.         res += rec(at + 1);
  26.     }
  27.    
  28.     if(s[at] != '0' and at + 1 < n) {
  29.         int num = (s[at] - '0') * 10 + (s[at + 1] - '0');
  30.         if(num <= 26) {
  31.             res += rec(at + 2);
  32.         }
  33.     }
  34.    
  35.     dp[at] = res;
  36.     return res;
  37.    
  38. }
  39. int main() {
  40.     ios::sync_with_stdio(false);
  41.     memset(dp, -1, sizeof dp);
  42.     cin >> s;
  43.    
  44.     n = (int) s.size();
  45.     cout << rec(0) << endl;
  46.     return 0;
  47. }
  48.  
Advertisement
Add Comment
Please, Sign In to add comment