Advertisement
Josif_tepe

Untitled

Mar 30th, 2022
698
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.13 KB | None
  1. #include <iostream>
  2. #include <cstring>
  3. using namespace std;
  4. string S;
  5. int k;
  6. int dp[105][105];
  7. bool cmp(string a, string b) {
  8.     if(a.size() > b.size()) return false;
  9.     if(a.size() < b.size()) return true;
  10.     if(a < b) return true;
  11.     if(a > b) return false;
  12.     if(a == b) return true;
  13.     return false;
  14. }
  15. int rec(int at, int k_left) {
  16.     if(at == S.size() - 1 and k_left == k) {
  17.         return 1;
  18.     }
  19.     if(at != -1 and dp[at][k_left] != -1) {
  20.         return dp[at][k_left];
  21.     }
  22.     int result = 0;
  23.     string tmp = "";
  24.     for(int i = at + 1; i < S.size(); i++) {
  25.         tmp += S[i];
  26.         if(tmp[0] == '0' and tmp.size() >= 2) {
  27.             continue;
  28.         }
  29.         if(cmp(tmp, "255")) {
  30.             result += rec(i, k_left + 1);
  31.         }
  32.         else {
  33.             break;
  34.         }
  35.     }
  36.     if(at != -1) {
  37.         dp[at][k_left] = result;
  38.     }
  39.     return  result;
  40. }
  41. int main()
  42. {
  43.     cin >> S >> k;
  44.     for(int i = 0; i < 105; i++) {
  45.         for(int j = 0; j < 105; j++) {
  46.             dp[i][j] = -1;
  47.         }
  48.     }
  49.     cout << rec(-1, 0) << endl;
  50.     return 0;
  51. }
  52. // 1234567 3
  53.  
Advertisement
RAW Paste Data Copied
Advertisement