読者です 読者をやめる 読者になる 読者になる

srupのメモ帳

競プロで解いた問題や勉強したことを記録していくメモ帳

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

その他コンテスト dp

問題

問題概要

省略

解法

単純に全ての状態を全探索すると、2nで無理。 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つでできるっぽい。

頭いい。

コード

#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;
}