Codeforces149D(카운트 구간 dp)

제목:
일련의 규칙을 제시하는 괄호 (괄호는 일치하는 것) 예를 들어 (() ()) 이 괄호의 정확한 일치는 첫 번째와 마지막, 두 번째와 세 번째, 네 번째와 다섯 번째이다.
지금 괄호를 염색하려면 이런 조건을 제시해야 한다. 1. 괄호는 염색하지 않고 파란색으로 염색하고 빨간색으로 염색할 수 있다.
2. 일치하는 괄호는 동시에 염색할 수 없지만 그 중 하나는 반드시 염색해야 한다.
3. 인접한 괄호는 같은 색으로 염색할 수 없으며 색칠을 하지 않아도 된다.
문제 풀이:
기억 최적화의 장점, 어떤 상태에 어떤 상태를 더해야 하는지, 그리고 새로운 검색, 기록.이 문제는 점차적인 추측으로는 쓰기가 매우 어렵다.
상태: dp[i][j][k][t] 왼쪽(i) 오른쪽(j) 구간 괄호가 k이고 t일 때 가장 큰 방안 수입니다.

#include<iostream>
#include<math.h>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<vector>
#include<map>
using namespace std;
typedef long long lld;
const int oo=0x3f3f3f3f;
const lld OO=1LL<<61;
const lld MOD=1000000007;
#define eps 1e-6
#define maxn 705
lld dp[maxn][maxn][3][3];
char str[maxn];
int mat[maxn],stack[maxn];
int n;

void Match()
{
    int top=0;
    for(int i=1;i<=n;i++)
    {
        if(str[i]=='(')
            stack[++top]=i;
        else
        {
            mat[i]=stack[top];
            mat[stack[top]]=i;
            --top;
        }
    }
}

void dfs(int i,int j)
{
    if(i+1==j)
    {
        dp[i][j][0][1]=1;
        dp[i][j][1][0]=1;
        dp[i][j][0][2]=1;
        dp[i][j][2][0]=1;
        return ;
    }
    if(mat[i]==j)
    {
        dfs(i+1,j-1);
        for(int l=0;l<3;l++)
        {
            for(int r=0;r<3;r++)
            {
                if(l!=1)
                    dp[i][j][0][1]=(dp[i][j][0][1]+dp[i+1][j-1][l][r]+MOD)%MOD;
                if(r!=1)
                    dp[i][j][1][0]=(dp[i][j][1][0]+dp[i+1][j-1][l][r]+MOD)%MOD;
                if(l!=2)
                    dp[i][j][0][2]=(dp[i][j][0][2]+dp[i+1][j-1][l][r]+MOD)%MOD;
                if(r!=2)
                    dp[i][j][2][0]=(dp[i][j][2][0]+dp[i+1][j-1][l][r]+MOD)%MOD;
            }
        }
    }
    else
    {
        int m=mat[i];
        dfs(i,m);
        dfs(m+1,j);
        for(int l=0;l<3;l++)
        {
            for(int r=0;r<3;r++)
            {
                for(int x=0;x<3;x++)
                {
                    for(int y=0;y<3;y++)
                    {
                        ///            
                        if(x==1&&y==1)continue;
                        if(x==2&&y==2)continue;

                        dp[i][j][l][r]=(dp[i][j][l][r]+(dp[i][m][l][x]*dp[m+1][j][y][r])%MOD+MOD)%MOD;
                    }
                }
            }
        }
    }
}

int main()
{
    while(scanf("%s",str+1)!=EOF)
    {
        n=strlen(str+1);
        memset(dp,0,sizeof dp);
        Match();
        dfs(1,n);
        lld ans=0;
        for(int l=0;l<3;l++)
            for(int r=0;r<3;r++)
                ans=(ans+dp[1][n][l][r]+MOD)%MOD;
        cout<<ans<<endl;
    }
    return 0;
}
/**
(())
(()())
()


*/