HDOJ 5479 Scaena Felix


タイトルリンク:HDOJ 5479
テストのグループtは、それぞれのグループは"("と")"からなる文字列Sをテストして、Sにサブカッコが一致しない最小の代価はいくらですかを闻きます.1つの代価は、一度に「(」を「)」に変更するか、逆に定義されます.
データ範囲:1≤|S|≤1000
Sのサブストリングにカッコが一致しないようにするには、Sを3つのケースにするしかありません.1.左かっこ「(....)」2.すべて右かっこ")……."3.左括弧、右括弧
参照コード:
#include <iostream>
#include <string>

using namespace std;

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        string st;
        cin >> st;
        int len = st.length();
        int l[len], r[len];
        for(int i = 0; i < len; ++i)//l[i] [0,i] ")" 
        {
            if(i == 0) l[i] = st[i] == '(';
            else if(st[i] == '(') l[i] = l[i - 1] + 1;
            else l[i] = l[i - 1];
        }
        for(int i = len - 1; i >= 0; --i)//r[i] [i,len - 1] "(" 
        {
            if(i == len - 1) r[i] = st[i] == ')';
            else if(st[i] == ')') r[i] = r[i + 1] + 1;
            else r[i] = r[i + 1];
        }
        int ans = 2e9;
        for(int i = 0; i < len; ++i)// 3 
            ans = min(ans, l[i] + r[i] - 1) ;
        cout << ans << endl;
    }
    return 0;
}