https://arena.topcoder.com/#/u/practiceCode/15329/27700/12155/2/314283

CuttingBitString.cpp

#include <bits/stdc++.h>

#define ll long long
#define sz(v) ((int) ((v).size()))
#define clr(v, d) memset(v, d, sizeof(v))
#define lp(i, n) for(int i = 0; i < (int)(n); ++i)
#define rep(i, v) for(int i = 0; i < sz(v); ++i)

using namespace std;

int n;
const int MAX = 55;
const int OO = 1e9;

const int POW_COUNT = 22;
string powers[] = {
"1",
"101",
"11001",
"1111101",
"1001110001",
"110000110101",
"11110100001001",
"10011000100101101",
"1011111010111100001",
"111011100110101100101",
"100101010000001011111001",
"10111010010000111011011101",
"1110100011010100101001010001",
"1001000110000100111001110010101",
"101101011110011000100000111101001",
"11100011010111111010100100110001101",
"10001110000110111100100110111111000001",
"1011000110100010101111000010111011000101",
"110111100000101101101011001110100111011001",
"100010101100011100100011000001001000100111101",
"10101101011110001110101111000101101011000110001",
"1101100011010111001001101011011100010111011110101"
};

string s;
int cache[MAX][MAX];

int minCut(int i, int last) {
    if(i == n) {
        if(i == last)
            return 0;
        return OO;
    }

    int &ret = cache[i][last];
    if(ret != -1)
        return ret;
    ret = OO;
    string tmp = s.substr(last, i-last+1);
    /*lp(j, tmp.length()) {
        if(tmp[j] == '1')
            break;
        tmp = tmp.substr(j+1);
    }*/
    //cout << tmp <<endl;
    if(s[last] == '1')
        lp(j, POW_COUNT) {
            if(tmp == powers[j]) {
                ret = 1+minCut(i+1, i+1);
                break;
            }
        }
    ret = min(ret, minCut(i+1, last));


    return ret;

}

class CuttingBitString {
public:
    int getmin(string s1) {
        s = s1;
        n = s.length();
        clr(cache, -1);
        int x = minCut(0, 0);
        return ( x == OO ? -1 : x );
    }
};

/*
int main() {
    int t;
    cin>>t;
    while(t--) {
        cin>>s;
        n = s.length();
        clr(cache, -1);
        int x = minCut(0, 0);
        cout << ( x == OO ? -1 : x )<< endl;
    }
    return 0;
}
*/