poj 1141 브래킷 시퀀스(구간 DP)

제목:http://poj.org/problem?id=1141
전재:http://blog.csdn.net/lijiecsu/article/details/7589877

합 법 적 인 괄호 서열 을 다음 과 같이 정의 합 니 다.
1.빈 서열 은 합 법 적 인 서열 이다.
2 만약 에 S 가 합 법 적 인 서열 이 라면(S)와[S]도 합 법 적 인 서열 이다.
3 A 와 B 가 합 법 적 인 서열 이 라면 AB 도 합 법 적 인 서열 이다.
예 를 들 어 아래 는 모두 합 법 적 인 괄호 서열 이다.
(), [], (()), ([]), ()[], ()[()]
아래 의 것 은 모두 불법 괄호 서열 이다.
(, [, ), )(, ([)], ([(]
'(',' ')', '[', ']'로 구 성 된 서열 을 찾 아 이 서열 을 하위 서열 로 하 는 최 단 합 법 적 인 서열 을 찾 아 라.

d[i][j]는 입력 서열 을 위해 아래 표 i 에서 아래 표 j 까지 최소한 괄호 를 얼마나 넣 어야 합 법 적 인 서열 이 될 수 있 습 니까?0<=i<=jc[i][j]는 입력 시퀀스 를 위해 아래 표 i 에서 아래 표 j 까지 의 차단 위 치 를 입력 합 니 다.끊 기지 않 으 면-1 입 니 다.
i===j 일 때 d[i][j]는 1 이다.
s[i]=='('&s[j]=')'또는 s[i]='['&s[j]='때 d[i][j]=d[i+1][j-1]
그렇지 않 으 면 d[i][j]=min{d[i][k]+d[k+1][j]}i<=k푸 시 방식 으로 d[i][j]를 계산 합 니 다.

결 과 를 출력 할 때 재 귀적 으로 print(0,len-1)를 출력 합 니 다.
출력 함 수 는 print(int i,int j)로 정의 되 며,출력 이 아래 표 i 에서 아래 표 j 까지 의 합 법 적 인 서열 을 표시 합 니 다.
i>j 시,출력 이 필요 없 이 바로 돌아 갑 니 다.
i==j 일 때 d[i][j]는 1 이 고 괄호 를 하나 더 넣 어야 합 니 다.만약 에 s[i]가'('또는')'이면'()'를 출력 하고 그렇지 않 으 면'[]'를 출력 합 니 다.
i>j 일 때 c[i][j]>=0 은 i 에서 j 까지 끊 겼 다 는 것 을 설명 하고 print(i,c[i][j])를 재 귀적 으로 호출 합 니 다.print(c[i][j]+1,j);
만약 c[i][j]<0 이 끊 기지 않 았 다 면 s[i]=='('이면 출력'(', print(i+1, j-1); 와")" 그렇지 않 으 면 출력"[" print(i+1, j-1);와"]"

#include <cstdio>
#include <cstring>

using namespace std;

int dp[107][107];
int c[107][107];
char ch[107];
int len ;

void mydp()
{
    memset(dp,0,sizeof(dp));
    memset(c,0,sizeof(c));

    int i,j,k,l;
    for(i = 0; i < len; i++) dp[i][i] = 1;
    int min;
    for(l = 1; l < len; l++)
        for(i = 0; i+l < len; i++)
            {
                j = i+l;
                min=dp[i][i] + dp[i+1][j];
                c[i][j] = i;
                for(k = i+1; k < j; k++)
                {
                    if(dp[i][k]+dp[k+1][j] < min)
                    {
                        min = dp[i][k] + dp[k+1][j];
                        c[i][j] = k;
                    }
                }
                dp[i][j] = min;

                if( (ch[i] == '(' && ch[j] == ')') || (ch[i] == '[' && ch[j] == ']') )
                {
                    if(dp[i+1][j-1] < min){
                        dp[i][j] = dp[i+1][j-1];
                        c[i][j] = -1;
                    }
                }
            }
}

void print(int i,int j)
{
    if(i > j) return;
    if(i == j)
    {
       if(ch[i]== '(' || ch[i] == ')') printf("()");
       else printf("[]");
    }
    else
    {
        if(c[i][j] >= 0)
        {
            print(i,c[i][j]);
            print(c[i][j]+1,j);
        }
        else
        {
            if(ch[i] == '(')
              {
                  printf("(");
                  print(i+1,j-1);
                  printf(")");
              }
            else
            {
                printf("[");
                print(i+1,j-1);
                printf("]");
            }
        }
    }
}

void printdp()
{
    for(int i = 0; i < len; i++)
        {for(int j = 0; j < len; j++)
        printf("%d ",dp[i][j]);
        printf("
");}
         printf("
");
         for(int i = 0; i < len; i++)
        {for(int j = 0; j < len; j++)
        printf("%d ",c[i][j]);
        printf("
");}
}
int main()
{
        scanf("%s",ch);
        len = strlen(ch);
        mydp();
      //  printdp();
        print(0,len-1);
        printf("
");

    return 0;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

POJ 2442 Sequence

Sequence Time Limit: 6000MS Memory Limit: 65536K Total Submissions: 6120 Accepted: 1897 Description Given m sequences, e...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

poj 1141 브래킷 시퀀스(구간 DP)

좋은 웹페이지 즐겨찾기