CF 149 D Coloring Brackets(구간 DP)

자기는 어떻게 구간DP를 해야 할지 생각도 못했어...나중에 본 다른 사람의...바로 통계 dp[l][r][i][j]l~r 구간에서 l는 i색을, r는 j색을 바르는 방법 개수는 일치하는 괄호를 만나면 바로 안쪽을 한 단위로 축소하는 것을 잊어버리는 것이다. 그렇지 않으면 구간을 두 단락으로 나눈다. l~p[l], p[l]+1~r 이 편은 ORZ를 상세하게 설명했다.http://blog.csdn.net/sdjzping/article/details/19160013

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<queue>
#include<stack>
#include<string>
#include<vector>
#include<map>
#include<set>
using namespace std;
#define rfor(i,a,b) for(i=a;i<=b;++i)
#define lfor(i,a,b) for(i=a;i>=b;--i)
#define sfor(i,a,h) for(i=h[a];i!=-1;i=e[i].next)
#define mem(a,b) memset(a,b,sizeof(a))
#define mec(a,b) memcpy(a,b,sizeof(b))
#define cheak(i) printf("%d ",i)
#define min(a,b) (a>b?b:a)
#define max(a,b) (a>b?a:b)
#define inf 0x3f3f3f3f
#define lowbit(x) (x&(-x))
typedef long long LL;
#define maxn 705
#define maxm maxn*maxn
#define lson(x) (splay[x].son[0])
#define rson(x) (splay[x].son[1])
#define mod 1000000007
LL dp[maxn][maxn][3][3];
int p[maxn],stac[maxn];
void fun(char *str,int n)
{
    int i,k=0;
    rfor(i,1,n)
    {
        if(str[i]=='(')
        stac[++k]=i;
        else
        {
            p[i]=stac[k];
            p[stac[k]]=i;
            k--;
        }
    }
}
void solve(int l,int r)
{
    int i,j,k,q;
    if(l>=r) return ;
    if(p[l]==r)
    {
        if(l==r-1)
        {
            dp[l][r][0][1]=1;
            dp[l][r][0][2]=1;
            dp[l][r][1][0]=1;
            dp[l][r][2][0]=1;
            return ;
        }
        solve(l+1,r-1);
         rfor(i,0,2)
          rfor(j,0,2)
          {
            if(i!=1) dp[l][r][1][0]=(dp[l][r][1][0]+dp[l+1][r-1][i][j])%mod;
            if(i!=2) dp[l][r][2][0]=(dp[l][r][2][0]+dp[l+1][r-1][i][j])%mod;
            if(j!=1) dp[l][r][0][1]=(dp[l][r][0][1]+dp[l+1][r-1][i][j])%mod;
            if(j!=2) dp[l][r][0][2]=(dp[l][r][0][2]+dp[l+1][r-1][i][j])%mod;
        }
    }
    else
    {
        int t=p[l];
        solve(l,t);
        solve(t+1,r);
        rfor(i,0,2)
         rfor(j,0,2)
          rfor(k,0,2)
           rfor(q,0,2)
           {
            if(!(q==1&&k==1||q==2&&k==2))
            dp[l][r][i][j]=(dp[l][r][i][j]+(dp[l][t][i][k]*dp[t+1][r][q][j])%mod)%mod;
        }
    }
}
char str[maxn];
int main()
{
    scanf("%s",str+1);
    int n=strlen(str+1);
    fun(str,n);
    mem(dp,0);
    solve(1,n);
    LL ans=0;
    int i,j;
    rfor(i,0,2)
     rfor(j,0,2)
     ans=(ans+dp[1][n][i][j])%mod;
    printf("%lld
",ans);
    return 0;
}