天下一プログラマーコンテスト2016予選B B - 天下一魔力発電

問題

問題概要

省略

解法

単純に全ての状態を全探索すると、2ⁿで無理。 dpで解きました。状態を決めるために、何文字目までで'('が何文字あり、最後に反転させた位置が同じであれば、同じ状態とみなせると考えた。
dp[i][j][k] := s[i]文字目まで見て、'('がj文字で、最後に文字を反転したのが、s[k]文字目の時のコストの最小値を入れて、ループを回した。また、'('の数は、常に現在見ている文字数の半分以上存在しなければならないという条件も加えている。漸化式は以下の4つを立てた。
dp[i + 1][j][i + 1] = min(dp[i][j][k] + i + 1 - k + 1, dp[i + 1][j][i + 1])
dp[i + 1][j + 1][k] = min(dp[i][j][k], dp[i + 1][j + 1][k])
dp[i + 1][j][k] = min(dp[i][j][k], dp[i + 1][j][k])
dp[i + 1][j + 1][i + 1] = min(dp[i][j][k] + i + 1 - k + 1, dp[i + 1][j + 1][i + 1])
また、i + 1 - k + 1というのは、前回反転さえた場所からカーソルを動かし、反転させたコストを加えている。

ミス

if(i + 1 > j * 2) continue;
などの部分を >= としていて、1wa また解法を思いついてから実装に1時間ぐらいかけてやっとACで遅解き2完。 状態数2つでできるっぽい。

Bはdp[t][j] := 最後にj番目をひっくり返して括弧の対応が+t余っている状態にするのに必要な反転回数の最小値　と定義してflyingTable でdp．
最後に min{ dp[0][j] + j ;0<=j<N } を取る．

— kuuso (@kuuso1) 2016年8月27日

頭いい。

コード

#include <iostream>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)

//dp[i][j][k] := s[i]文字目まで見て、'('がj文字で、最後に文字を反転したのが
//s[k]文字目の時のコストの最小値
int dp[110][55][110];
const int INF = 1e9;
int main(void){
    rep(i, 110)rep(j, 55)rep(k, 110) dp[i][j][k] = INF;

    string s; cin >> s;
    int n = s.size();
    if(s[0] == '(')dp[0][1][0] = 0;
    else dp[0][1][0] = 1;
    for (int i = 0; i < n - 1; ++i){
        for (int j = 0; j <= n / 2; ++j){
            for (int k = 0; k < n; ++k){
                if(dp[i][j][k] == INF)  continue;
                if(s[i + 1] == '('){
                    //変更
                    if(i + 1 > j * 2) continue;
                    dp[i + 1][j][i + 1] = min(dp[i][j][k] + i + 1 - k + 1, dp[i + 1][j][i + 1]);
                    //そのまま
                    if(i + 1 > (j + 1) * 2) continue;
                    dp[i + 1][j + 1][k] = min(dp[i][j][k], dp[i + 1][j + 1][k]);
                }else if(s[i + 1] == ')'){
                    //そのまま
                    if(i + 1 > j * 2) continue;
                    dp[i + 1][j][k] = min(dp[i][j][k], dp[i + 1][j][k]);
                    //変更
                    if(i + 1 > (j + 1) * 2) continue;
                    dp[i + 1][j + 1][i + 1] = min(dp[i][j][k] + i + 1 - k + 1, dp[i + 1][j + 1][i + 1]);
                }
            }
        }
    }

    int ans = INF;
    for (int i = 0; i < n; ++i){
        ans = min(ans, dp[n - 1][n / 2][i]);
    }
    cout << ans << endl;
    return 0;
}