Advertisement
Josif_tepe

Untitled

Jan 26th, 2022
963
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.21 KB | None | 0 0
  1. class IpAddresses
  2. {
  3.   public:
  4.     int dp[105][105];
  5.     string n;
  6.     int k;
  7.     bool cmp(string A, string B) {
  8.         if(A.size() > B.size()) {
  9.             return false;
  10.         }
  11.         if(A.size() < B.size()) {
  12.             return true;
  13.         }
  14.         if(A < B) {
  15.             return true;
  16.         }
  17.         if(A == B) {
  18.             return true;
  19.         }
  20.         return false;
  21.     }
  22.     int rec(int i, int br) {
  23.         if(i == n.size() - 1 and k == br) {
  24.             return 1;
  25.         }
  26.         if(i != -1 and dp[i][br] != -1) {
  27.             return dp[i][br];
  28.         }
  29.         int result = 0;
  30.         string tmp = "";
  31.         for(int j = i + 1; j < n.size(); j++) {
  32.             tmp += n[j];
  33.             if(tmp.size() >= 2 and tmp[0] == '0') {
  34.                 continue;
  35.             }
  36.             if(cmp(tmp, "255")) {
  37.                 result += rec(j, br + 1);
  38.                 result %= 1000000007;
  39.             }
  40.             else {
  41.                 break;
  42.             }
  43.            
  44.         }
  45.         return dp[i][br] = result;
  46.     }
  47.     int count( string S, int K )
  48.     {
  49.         n = S;
  50.         k = K;
  51.         memset(dp, -1, sizeof dp);
  52.         return rec(-1, 0);
  53.      
  54.     }
  55. };
  56.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement