ARC036 C問題 偶数ジェネレータ

dpなんだけど、かなり上手くやらないとTLEする難しい問題。

dpは現在の状態を上手く簡単に表すことでいろんな場合を統合して扱うものなので、今回も現在の状態をより簡単に表す方法を探さないといけない。

'0'を-1, '1'を+1としてグラフにして見ると、これって実はそのグラフのminとmaxと現在の値だけで現在の状態を簡潔に表すことができるということがわかる。よってこれらを使いたいのだが、すると、
dp[今現在何文字目か][min][max][current]というdpになってしまってO(N*K^3)。
よって間に合わない。しかし、実際にはmax-minをdiffにまとめてしまっても問題ない。
よってO(N*K^2)で間に合う。
ARC036 - あるごりずむのおべんきょう
これがすごいわかりやすい気がする。

まぁdpは状態を簡潔に表すことが最重要なのかなぁ。

ということでコード

    int N, K;
    cin >> N >> K;
    string S;
    cin >> S;
    //number、max_diff、current
    int dp[N+1][K+1][K+1];
    memset(dp, -1, sizeof(dp));
    dp[0][0][0] = 1;
    for(int i=0; i<N; i++){
        for(int j=0; j<=K; j++){
            for(int k=0; k<=K; k++){
                if(dp[i][j][k] == -1) continue;
                if(S[i] != '1'){
                    if(k == 0){
                        if(j < K){
                            if(dp[i+1][j+1][k] == -1) dp[i+1][j+1][k] = dp[i][j][k];
                            else dp[i+1][j+1][k] += dp[i][j][k];
                            dp[i+1][j+1][k] %= mod;
                        }
                    }else{
                        if(dp[i+1][j][k-1] == -1) dp[i+1][j][k-1] = dp[i][j][k];
                        else dp[i+1][j][k-1] += dp[i][j][k];
                        dp[i+1][j][k-1] %= mod;
                    }
                }
                if(S[i] != '0'){
                    if(k == j){
                        if(j < K){
                            if(dp[i+1][j+1][k+1] == -1) dp[i+1][j+1][k+1] = dp[i][j][k];
                            else dp[i+1][j+1][k+1] += dp[i][j][k];
                            dp[i+1][j+1][k+1] %= mod;
                        }
                    }else{
                        if(dp[i+1][j][k+1] == -1) dp[i+1][j][k+1] = dp[i][j][k];
                        else dp[i+1][j][k+1] += dp[i][j][k];
                        dp[i+1][j][k+1] %= mod;
                    }
                }
            }
        }
    }
    int res = 0;
    for(int i=0; i<=K; i++){
        for(int j=0; j<=K; j++){
            if(dp[N][i][j] == -1) continue;
            res += dp[N][i][j];
            res %= mod;
        }
    }
    cout << res << endl;