Advertisement
Josif_tepe

Untitled

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