SRM555 Div2 Medium

555

DP[何桁目まで]

view plainprint?

1. string m5(string a)  
2. {  
3.   string b = a;  
4.   a = a + "00";  
5.   b = "00" + b;  
6.   reverse(a.begin(), a.end());  
7.   reverse(b.begin(), b.end());  
8.   vector<char> v;  
9.   const int size = b.size();  
10.   int c = 0;  
11.   for (int i = 0; i < size; ++i) {  
12.     int n = (a[i] == '1') + (b[i] == '1') + c;  
13.     if (n == 0) {  
14.       v.push_back('0');  
15.       c = 0;  
16.     } else if (n == 1) {  
17.       v.push_back('1');  
18.       c = 0;  
19.     } else if (n == 2) {  
20.       v.push_back('0');  
21.       c = 1;  
22.     } else if (n == 3) {  
23.       v.push_back('1');  
24.       c = 1;  
25.     }  
26.   }  
27.   if (c) v.push_back('1');  
28.   reverse(v.begin(), v.end());  
29.   string ret;  
30.   for (int i = 0; i < v.size(); ++i) {  
31.     ret += v[i];  
32.   }  
33.   return ret;  
34. }  
35.   
36. bool match(string a, int base, string b)  
37. {  
38.   if (base + b.size() <= a.size()) {  
39.     for (int i = 0; i < b.size(); ++i) {  
40.       if (a[i + base] != b[i]) return false;  
41.     }  
42.     return true;  
43.   }  
44.   return false;  
45. }  
46.   
47. class CuttingBitString {  
48. public:  
49.   int getmin(string S)  
50.   {  
51.     vector<string> v;  
52.     v.push_back("1");  
53.     v.push_back("101");  
54.   
55.     while (v.back().size() <= 50) {  
56.       v.push_back(m5(v.back()));  
57.     }  
58.   
59.     const int inf = 1 << 28;  
60.     const int N = S.size() + 1;  
61.     int dp[N];  
62.     fill(dp, dp + N, inf);  
63.     dp[0] = 0;  
64.   
65.     for (int i = 0; i < N; ++i) {  
66.       for (int j = 0; j < v.size(); ++j) {  
67.         if (match(S, i, v[j])) {  
68.           dp[i + v[j].size()] = min(dp[i + v[j].size()], dp[i] + 1);  
69.         }  
70.       }  
71.     }  
72.   
73.     int ret = dp[N - 1];  
74.     return ret == inf ? -1 : ret;  
75.   }  
76. };  

string m5(string a)
{
  string b = a;
  a = a + "00";
  b = "00" + b;
  reverse(a.begin(), a.end());
  reverse(b.begin(), b.end());
  vector<char> v;
  const int size = b.size();
  int c = 0;
  for (int i = 0; i < size; ++i) {
    int n = (a[i] == '1') + (b[i] == '1') + c;
    if (n == 0) {
      v.push_back('0');
      c = 0;
    } else if (n == 1) {
      v.push_back('1');
      c = 0;
    } else if (n == 2) {
      v.push_back('0');
      c = 1;
    } else if (n == 3) {
      v.push_back('1');
      c = 1;
    }
  }
  if (c) v.push_back('1');
  reverse(v.begin(), v.end());
  string ret;
  for (int i = 0; i < v.size(); ++i) {
    ret += v[i];
  }
  return ret;
}

bool match(string a, int base, string b)
{
  if (base + b.size() <= a.size()) {
    for (int i = 0; i < b.size(); ++i) {
      if (a[i + base] != b[i]) return false;
    }
    return true;
  }
  return false;
}

class CuttingBitString {
public:
  int getmin(string S)
  {
    vector<string> v;
    v.push_back("1");
    v.push_back("101");

    while (v.back().size() <= 50) {
      v.push_back(m5(v.back()));
    }

    const int inf = 1 << 28;
    const int N = S.size() + 1;
    int dp[N];
    fill(dp, dp + N, inf);
    dp[0] = 0;

    for (int i = 0; i < N; ++i) {
      for (int j = 0; j < v.size(); ++j) {
        if (match(S, i, v[j])) {
          dp[i + v[j].size()] = min(dp[i + v[j].size()], dp[i] + 1);
        }
      }
    }

    int ret = dp[N - 1];
    return ret == inf ? -1 : ret;
  }
};