AtCoder Regular Contest 036 C - 偶然ジェネレータ

解けなかったの悔しい。

問題:C: 偶然ジェネレータ - AtCoder Regular Contest 036 | AtCoder

解法:dp[pos][diff0][diff1]=(posの文字を見ている時点で(0の数-1の数)の最大値がdiff0,(1の数-0の数)の最大値がdiff1であるような場合の数)とすると,次の数が0か1かによって状態遷移ができる。詳しいことはソースコード参照。

const int MAXN = 305;
const ll MOD = 1e9+7;
ll dp[MAXN][MAXN][MAXN];
int N, K;
string s;

ll dfs(int cur, int diff0, int diff1) {
    if (diff0 > K) return 0;
    if (diff1 > K) return 0;
    if (cur == N) return 1;
    ll& ret = dp[cur][diff0][diff1];
    if (ret >= 0) return ret;
    ret = 0;
    if (s[cur] == '1' || s[cur] == '?') {
        ret += dfs(cur+1, max(0, diff0-1), diff1+1);
        ret %= MOD;
    }
    if (s[cur] == '0' || s[cur] == '?') {
        ret += dfs(cur+1, diff0+1, max(0, diff1-1));
        ret %= MOD;
    }
    return ret;
}

int main() {
    cin >> N >> K;
    cin >> s;
    memset(dp, -1, sizeof(dp));
    cout << dfs(0, 0, 0) << endl;
    return 0;
}