구간 dp 학습편 (괄호 일치)

괄호 일치, 제목 요구에 따라 최대 괄호 일치수 구하기
HRBUST - 1834
예를 들어 이 문제는 석자 합병과 달리 제목이 정한 괄호의 일치 상황은 우리가 스스로 갱신해야 한다. 석자 합병에서 정한 수치와 직접적이지 않다. 이것은 우리가 이전의 상태 이동 방정식(dp[i][j]=max(dp[i][j], dp[i][k]+dp[k+1][j])을 갱신하기 전에 현재 구간의 괄호 일치 상황을 갱신하는 판별식(s[i]=s[j]?2:0)을 추가해야 한다.이렇게 하면 더 큰 구간을 갱신하는 동시에 가장 좋은 결과를 찾을 수 있다

#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
int dp[105][105];
int main()
{
    char a[105];
    while(scanf("%s",a) != EOF)
    {
        int n = strlen(a);
        memset(dp, 0, sizeof(dp));
        for(int len = 1; len < n; len ++)
            for(int i = 0; i + len < n; i ++)
        {
            int j = len + i;
            if((a[i] == '(' && a[j] == ')')|| (a[i] == '[' && a[j] == ']'))
                dp[i][j] = dp[i+1][j-1] + 2;
            for(int k = i; k < j; k ++)
                dp[i][j] = max(dp[i][k]+dp[k+1][j],dp[i][j]);
        }
        printf("%d
",dp[0][n-1]);
    }
    return 0;
}

괄호 일치(둘)
괄호가 일치합니다.같다
괄호를 얼마나 넣어야 완전히 일치하는지 묻고 마지막 출력을 (n-dp[0][n-1])으로 바꾸면 됩니다.

#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
int dp[105][105];
int main()
{
    char a[105];
    int t;
    scanf("%d",&t);
    while(t --)
    {
        scanf("%s",a);
        int n = strlen(a);
        memset(dp, 0, sizeof(dp));
        for(int len = 1; len < n; len ++)
            for(int i = 0; i + len < n; i ++)
        {
            int j = len + i;
            if((a[i] == '(' && a[j] == ')')|| (a[i] == '[' && a[j] == ']'))
                dp[i][j] = dp[i+1][j-1] + 2;
            for(int k = i; k < j; k ++)
                dp[i][j] = max(dp[i][k]+dp[k+1][j],dp[i][j]);
        }
        printf("%d
",n - dp[0][n-1]);
    }
    return 0;
}

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

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

HDU6212 Zuma(구간 dp)

전송문 1 전송문 2 Think about the Zuma Game.You have a row of at most 200 black(0) or white(1) balls on the table at the start...

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

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

구간 dp 학습편 (괄호 일치)

좋은 웹페이지 즐겨찾기