A题简单DP。
由于两段合法分割可以组合成一个更大的合法分割,所以此DP为和式DP。
状态转移方程为

if (isfive(s, j, i)) dp[i] = min(dp[i], dp[j] + 1);
const int mx = 55;

int dp[mx];

class CuttingBitString
{
    public:
        bool isfive(string &s, int beg, int end)
        {
            if (s[beg] == '0') return false;
            ll ans = 0LL;
            int i;
            Forr(i, beg, end) ans = (ans << 1LL) + (ll)(s[i] & 1);
            while (ans % 5LL == 0LL) ans /= 5LL;
            return ans == 1LL;
        }

        int getmin(string s)
        {
            int i, j, n = s.size();
            mem(dp, 0x3f);
            dp[0] = 0; /// dp[i]表示s[0...(i-1)]的最小合法分割数
         Forr(i, 1, n + 1) For(j, i) if (isfive(s, j, i)) dp[i] = min(dp[i], dp[j] + 1);
            return dp[n] == inf ? -1 : dp[n];
        }
};

Comments

comments powered by Disqus