Codeforces 149D. Coloring Brackets

正文索引 [隐藏]

题目翻译
题解
代码

传送门：http://codeforces.com/contest/149/problem/D

题目翻译

一个符合匹配的括号序列，匹配的两个括号只能有一个有颜色（红色或者蓝色），相邻的符号若有颜色颜色不同。求不同的方案数。

题解

区间DP
DP[left][right][lc][rc]表示left~right的区间内左边颜色为lc,右边颜色为rc的方案数。
然后因为有重复，所以我们每次合并左右两个大区间的时候，只选择右边是刚好被一对括号包括的区间。

代码

#include<cstdio>
#include<cstring>
using namespace std;
const int Maxn=700;
const long long Mod=1000000007;
char str[Maxn+5];
int N;
long long dp[Maxn+5][Maxn+5][5][5];
int stk[Maxn+5];
int top;
int ind[Maxn+5];
int nume;
int pos[Maxn+5];
int main(){
    freopen("in.txt","r",stdin);
    scanf("%s",str);
    N=strlen(str);
    memset(dp,0,sizeof(dp));
    //memset(mtdp,0,sizeof(mtdp));
    top=nume=0;
    for (int i=1;i<=N;i++){
        if (str[i-1]=='('){
            nume++;
            ind[i]=nume;
            pos[nume]=i;
            stk[++top]=nume;
        }else{
            ind[i]=stk[top--];
        }
    }
    for (int i=1;i<N;i++){
        if (ind[i]==ind[i+1]){
            dp[i][i+1][0][1]=dp[i][i+1][0][2]=1;
            dp[i][i+1][1][0]=dp[i][i+1][2][0]=1;
        }
    }
    for (int len=4;len<=N;len+=2){
        for (int left=1;left<=N;left++){
            int right=left+len-1;
            if (right>N) break;
            if (ind[left]==ind[right]){
                for (int ilc=0;ilc<=2;ilc++)
                    for (int irc=0;irc<=2;irc++){
                        //if (irc*ilc!=0 || irc+ilc==0) continue;
                        for (int olc=0;olc<=2;olc++)
                            for (int orc=0;orc<=2;orc++){
                                if (olc*orc!=0 || olc+orc==0) continue;
                                if ((olc+ilc>0 && olc==ilc) || (orc+irc>0 && orc==irc)) continue;
                                dp[left][right][olc][orc]=(dp[left][right][olc][orc]+dp[left+1][right-1][ilc][irc])%Mod;
                            }
                    }
            }
            //for (int mid=left;mid<right;mid++){
                int mid=pos[ind[right]];
                if (mid==right) continue;
                if (!(left<=mid && mid<=right)) continue;
                mid--;
                if (ind[mid+1]!=ind[right]) continue;
                for (int llc=0;llc<=2;llc++)
                for (int lrc=0;lrc<=2;lrc++)
                for (int rlc=0;rlc<=2;rlc++)
                for (int rrc=0;rrc<=2;rrc++){
                    if (lrc==rlc && lrc+rlc>0) continue;
                    dp[left][right][llc][rrc]=(
                        dp[left][right][llc][rrc] +
                        dp[left][mid][llc][lrc] * dp[mid+1][right][rlc][rrc] % Mod
                    )%Mod;
                }
            //}
        }
    }
    long long Ans=0;
    for (int lc=0;lc<=2;lc++)
        for (int rc=0;rc<=2;rc++)
            Ans=(Ans+dp[1][N][lc][rc])%Mod;
    printf("%I64d\n",Ans);
    return 0;
}

#include<cstdio>

#include<cstring>

using namespace std;

const int Maxn=700;

const long long Mod=1000000007;

char str[Maxn+5];

int N;

long long dp[Maxn+5][Maxn+5][5][5];

int stk[Maxn+5];

int top;

int ind[Maxn+5];

int nume;

int pos[Maxn+5];

int main(){

freopen("in.txt","r",stdin);

scanf("%s",str);

N=strlen(str);

memset(dp,0,sizeof(dp));

//memset(mtdp,0,sizeof(mtdp));

top=nume=0;

for (int i=1;i<=N;i++){

if (str[i-1]=='('){

nume++;

ind[i]=nume;

pos[nume]=i;

stk[++top]=nume;

}else{

ind[i]=stk[top--];

}

for (int i=1;i<N;i++){

if (ind[i]==ind[i+1]){

dp[i][i+1][0][1]=dp[i][i+1][0][2]=1;

dp[i][i+1][1][0]=dp[i][i+1][2][0]=1;

}

for (int len=4;len<=N;len+=2){

for (int left=1;left<=N;left++){

int right=left+len-1;

if (right>N) break;

if (ind[left]==ind[right]){

for (int ilc=0;ilc<=2;ilc++)

for (int irc=0;irc<=2;irc++){

//if (irc*ilc!=0 || irc+ilc==0) continue;

for (int olc=0;olc<=2;olc++)

for (int orc=0;orc<=2;orc++){

if (olc*orc!=0 || olc+orc==0) continue;

if ((olc+ilc>0 && olc==ilc) || (orc+irc>0 && orc==irc)) continue;

dp[left][right][olc][orc]=(dp[left][right][olc][orc]+dp[left+1][right-1][ilc][irc])%Mod;

}

//for (int mid=left;mid<right;mid++){

int mid=pos[ind[right]];

if (mid==right) continue;

if (!(left<=mid && mid<=right)) continue;

mid--;

if (ind[mid+1]!=ind[right]) continue;

for (int llc=0;llc<=2;llc++)

for (int lrc=0;lrc<=2;lrc++)

for (int rlc=0;rlc<=2;rlc++)

for (int rrc=0;rrc<=2;rrc++){

if (lrc==rlc && lrc+rlc>0) continue;

dp[left][right][llc][rrc]=(

dp[left][right][llc][rrc] +

dp[left][mid][llc][lrc] * dp[mid+1][right][rlc][rrc] % Mod

)%Mod;

}

//}

}

long long Ans=0;

for (int lc=0;lc<=2;lc++)

for (int rc=0;rc<=2;rc++)

Ans=(Ans+dp[1][N][lc][rc])%Mod;

printf("%I64d\n",Ans);

return 0;

}

一	二	三	四	五	六	日
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30	31

WNJXYKの博客

喂你脚下有坑