DP - 구간 DP - Brackets - POJ - 2955

DP - 구간 DP - Brackets - POJ - 2955

제목:
다음 방법으로 합법적인 괄호 문자열을 정의합니다.빈 꿰미는 합법적이다.만약 S가 합법적이라면 (S)와 [S]도 모두 합법적이다.만약 A와 B가 합법적이라면, AB는 합법적인 문자열이다.올바른 괄호 문자열을 다음과 같이 정의합니다.\1.빈 문자열은 합법적입니다\2.만약 S가 합법적이라면 (S)와[S]도 모두 합법적이다\3.만약 A와 B가 합법적이라면 AB는 합법적인 문자열이다.다음 방법으로 합법적인 괄호 문자열을 정의합니다.빈 꿰미는 합법적이다.만약 S가 합법적이라면 (S)와[S]도 모두 합법적이다.만약 A와 B가 합법적이라면 AB는 합법적인 문자열이다.
현재 "()"과 "[]"만 포함하는 괄호 서열 s를 지정합니다. 서열 s의 합법적인 괄호 문자 서열의 최대 길이를 요구합니다.현재 "()"과 "[]"만 포함하는 괄호 서열 s를 지정합니다. 서열 s의 합법적인 괄호 문자 서열의 최대 길이를 요구합니다.현재 "()"과 "[]"만 포함하는 괄호 서열 s를 지정합니다. 서열 s의 합법적인 괄호 문자 서열의 최대 길이를 요구합니다.

Sample Input：
((()))
()()()
([]])
)[)(
([][][)
end

Sample Output：
6
6
4
0
6

데이터 범위:
시퀀스 길이 < = 100 T i m e l i t: 1000 m s, M e m o r y l i m i t: 65536 k B 시퀀스 길이 | s| <=100\Time\limit: 1000\ms, Memory\limit: 65536\kB 시퀀스 길이 <=100Time limit: 1000ms, Memory limit: 65536 kB 시퀀스 길이
분석:
이 문제는 합법적인 서열의 최대 길이를 구하는 것이기 때문에 창고로 괄호를 매칭할 수 없습니다.이 문제는 합법적인 서열의 최대 길이를 구하는 것이기 때문에 창고로 괄호를 매칭할 수 없습니다.이 문제는 합법적인 서열의 최대 길이를 구하는 것이기 때문에 창고로 괄호를 매칭할 수 없습니다.
사실상 합법적인 괄호의 계산은 서로 독립적이다.사실상 합법적인 괄호의 계산은 서로 독립적이다.사실상 합법적인 괄호의 계산은 서로 독립적이다.
구간 D P로 계산할 수 있습니다.구간 DP를 사용하여 계산할 수 있습니다.구간 DP를 사용하여 계산할 수 있습니다.
상태 표시: f[i][j]: 구간 [i, j]의 합법적인 괄호 수량의 최대값.상태 표시: f[i][j]: 구간 [i, j]의 합법적인 괄호 수량의 최대값.상태 표시: f[i][j]: 구간 [i, j]의 합법적인 괄호 수량의 최대값.
상태 계산: 구간 [l,r] 내의 합법적인 괄호 수량은 [l,k]와 [k+1,r] 두 부분으로 나눌 수 있으며, k는 경계점, k∈[l,r-3]로 나눌 수 있다.상태 계산:\구간 [l, r] 내의 합법적인 괄호 수량은 [l, k]와 [k+1, r] 두 부분으로 나눌 수 있고 k는 경계점, k∈[l, r-1]이다.상태 계산: 구간 [l, r] 내의 합법적인 괄호 수량은 [l, k]와 [k+1, r] 두 부분으로 나눌 수 있고 k는 경계점, k∈[l, r-3]로 나눌 수 있다.즉 f [l] [r] = m a x (f [l] [k] + f [k + 1] [r]).즉 f[l][r]=max(f[l][k]+f[k+1][r])이다.즉 f[l][r]=max(f[l][k]+f[k+1][r])이다.
특히 k=r일 때 전체 구간의 최대치를 구하는 것은 두 가지 상황이 있다. 특히 k=r일 때 전체 구간의 최대치를 구하는 것은 두 가지 상황이 있다. 특히 k=r일 때 전체 구간의 최대치를 구하는 것은 두 가지 상황이 있다.
①, s[l] ≠ s[r]이면 f[l] [r] = f[l+1] [r-3-1].②、s[l]=s[r], f[l][r] = f[l+1] [r-3-1] + 2.\①、s[l]≠s[r]이면 f[l][r]=f[l+1][r-1].\②、s[l]=s[r]이면 f[l][r]=f[l+1][r-1]+2.①、s[l]=s[r], f[l][r]=f[l+1][r-1].②、s[l]=s[r]이면 f[l][r]=f[l+1][r-3-1]+2.
마지막으로 각 길이가 len인 구간 [l,r]에 대해 매거 경계점 k로 최대치를 f[l][r]로 업데이트하면 된다.마지막으로 각 길이가len인 구간 [l,r]에 대해 매개 경계점 k로 최대치를 f[l][r]로 업데이트하면 됩니다.마지막으로 각 길이가len인 구간 [l,r]에 대해 매개 경계점 k로 최대치를 f[l][r]로 업데이트하면 됩니다.
코드:

#include
#include
#include

using namespace std;

const int N=110;

char s[N];
int f[N][N];  

bool check(int l,int r)
{
    if( (s[l]=='('&&s[r]==')')||(s[l]=='['&&s[r]==']') )return true;
    return false;
}

int main()
{
    while(~scanf("%s",s+1),strcmp("end",s+1))
    {
        memset(f,0,sizeof f);
        int n=strlen(s+1);
        
        for(int len=2;len<=n;len++)
            for(int l=1;l+len-1<=n;l++)
            {
                int r=l+len-1;
                f[l][r]=f[l+1][r-1];
                if(check(l,r)) f[l][r]+=2;
                for(int k=l;k<r;k++) f[l][r]=max(f[l][r],f[l][k]+f[k+1][r]);
            }
            
        cout<<f[1][n]<<endl;
    }
    
    return 0;
}