TopCoder SRM 589: FlippingBitsDiv1

問題文

public class FlippingBitsDiv1
{
    public int getmin(string[] _S, int M)
    {
        string S = String.Concat(_S);
        int N = S.Length;
        int L = (N - 1) / M + 1;
        int ans = int.MaxValue;
        if (M <= 18)
        {
            for (int i = 0; i < (1 << M); i++)
            {
                var dp = new int[L + 1, 2];
                dp[0, 1] = 1 << 28;
                for (int j = 0; j < L; j++)
                {
                    int flip = 0, all = 0;
                    for (int k = 0; k < M && j * M + k < N; k++)
                    {
                        if (((i & (1 << k)) != 0) != (S[j * M + k] == '1')) flip++;
                        all++;
                    }
                    dp[j + 1, 0] = Math.Min(dp[j, 0] + flip, dp[j, 1] + flip);
                    dp[j + 1, 1] = Math.Min(dp[j, 0] + all - flip + (j > 0 ? 2 : 1), dp[j, 1] + all - flip);
                }
                ans = Math.Min(ans, Math.Min(dp[L, 0], dp[L, 1]));
            }
        }
        else
        {
            for (int i = 0; i < (1 << L); i++)
            {
                int sub = 0;
                for (int j = 0; j < M; j++)
                {
                    int cnt0 = 0;
                    int cnt1 = 0;
                    for (int k = j, l = 0; k < N; k += M, l++)
                    {
                        bool fliped = (i & (1 << l)) != 0;
                        if (S[k] == '1' ^ fliped) cnt1++; else cnt0++;
                    }
                    sub += Math.Min(cnt0, cnt1);
                }
                bool pre = false;
                for (int j = 0; j < L; j++)
                {
                    if ((i & (1 << j)) != 0)
                    {
                        if (!pre) sub += (j > 0 ? 2 : 1);
                        pre = true;
                    }
                    else
                    {
                        pre = false;
                    }
                }
                ans = Math.Min(ans, sub);
            }
        }
        return ans;
    }
}