Advertisement
Josif_tepe

Untitled

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