SRM555 Div1 Easy - CuttingBitString

問題

長さnで '0' と '1' のみからなる文字列sが与えられる
これを2進数として見るとき、全ての部分列がleading-zeroなしで5の冪乗になるようにいくつかの部分列に分けたい
最小でいくつの部分列に分ける必要があるか求めよ
不可能な場合は-1

1 <= n <= 50

解法

s[L,r]の左端が0じゃなくて5の冪乗になってたら頂点Lから頂点r+1への辺を引く
これを全L,rでやって出来たグラフでdfs

class CuttingBitString {
public:
	vector<int> e[55];
	int d[55];

	void rec(int v, int dis) {
		d[v] = dis;
		each(i,e[v]) rec(i,dis+1);
	}

	int getmin(string s) {
		set<ll> p;
		ll t = 1;
		while (t<(1ll<<55)) p.insert(t), t *= 5;
		int n = s.size();
		rep(i,n) reps(j,i,n) if (s[i]!='0') {
			ll sum = 0;
			reps(k,i,j+1) sum <<= 1, sum |= s[k]-'0';
			if (p.count(sum)) e[i].push_back(j+1);
		}
		rep(i,55) d[i] = 1<<30;
		rec(0,0);
		return (d[n]==1<<30 ? -1 : d[n]);
	}
};