本文最后更新于:2020年4月13日 早上

题目分析

如果仅搜索所有状态,则$2^n$是不可能的。只能用dp解决。为了确定状态,我们认为,如果直到该字符为止有任意数量的’(’字符,并且最后一个倒置位置相同,则可以将其视为相同状态
Dp [i] [j] [k]: =查看s [i]字符,“(”是j字符,最后倒置的字符是s [k]字符。它还添加了一个条件,即’(’的数量必须始终至少是当前正在查看的字符数量的一半。设置了以下四个重复公式.

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是上次翻转位置的光标要增加冲销的成本。

$Code$

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

The end。


本文在 CC BY-NC-ND 4.0( https://creativecommons.org/licenses/by-nc-nd/4.0/deed.zh )协议 的前提下,禁止超过文章30%字数的摘录(对于不超过文章30%字数的摘录,要求在醒目位置注明原文作者与原文链接),同时,在未经作者本人手写签名许可的情况下,禁止任何形式的全文转载,禁止发布任何基于本文的再创作。

题解 AT1307 【億マス計算】 上一篇
题解 AT733 【風力観測】 下一篇
本博客采用 xCss 的 Valine 评论系统,搭配了 Valine-Admin,垃圾评论将会被过滤。所以在评论的时候,请注意您的语言。如果您的评论被过滤但并非垃圾评论,请发邮件到 luosiweimail@gmail.com 进行申诉。