当前位置：首页 > news >正文

题解：洛谷 CF149D Coloring Brackets

news 2026/5/28 14:30:47

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

洛谷：CF149D Coloring Brackets - 洛谷

【题目描述】

给出一个配对的括号序列（如 “(())() \texttt{(())()}(())()”、“() \texttt{()}()” 等，“)() \texttt{)()})()”、“(() \texttt{(()}(()”是不符合要求的），对该序列按照以下方法染色。

一个括号可以染成红色、蓝色或者不染色。
一对匹配的括号需要且只能将其中一个染色。
相邻两个括号颜色不能相同（但都可以不染色）。

求符合条件的染色方案数，对1000000007 10000000071000000007取模。

【输入】

一行一个字符串s ss，表示括号序列（2 ⩽ ∣ s ∣ ⩽ 700 2 \leqslant |s| \leqslant 7002⩽∣s∣⩽700）。

【输出】

一个数字，表示染色的方案数（对1000000007 10000000071000000007取模）。

【输入样例】

(())

【输出样例】

【算法标签】

#提高plus #区间DP

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=705,mod=1e9+7;// 定义常量和模数intn,match[N],ans;// n: 括号序列长度，match: 匹配括号的位置，ans: 答案intf[N][N][3][3];// DP数组，f[i][j][x][y]表示区间[i,j]的染色方案数，i染x色，j染y色string s;// 括号序列stack<int>stk;// 用于括号匹配的栈signedmain(){cin>>s;// 输入括号序列n=s.length();// 获取长度s=" "+s;// 在字符串前加空格，使下标从1开始for(inti=1;i<=n;i++)// 括号匹配{if(s[i]=='(')// 左括号入栈stk.push(i);else{// 右括号匹配match[stk.top()]=i;// 记录匹配位置match[i]=stk.top();stk.pop();// 弹出栈顶左括号}}// 区间DPfor(intlen=2;len<=n;len++)// 枚举区间长度for(inti=1;i+len-1<=n;i++)// 枚举区间起点{intj=i+len-1;// 区间终点if(i+1==j)// 区间长度为2，即一对括号{// 相邻括号的合法染色方案f[i][j][0][1]=f[i][j][0][2]=f[i][j][1][0]=f[i][j][2][0]=1;continue;}if(match[i]==j)// i和j是匹配的括号{for(intx=0;x<=2;x++)for(inty=0;y<=2;y++){// 枚举内部区间的染色if(y!=1)// 右括号不能染1f[i][j][0][1]=(f[i][j][0][1]+f[i+1][j-1][x][y])%mod;if(y!=2)// 右括号不能染2f[i][j][0][2]=(f[i][j][0][2]+f[i+1][j-1][x][y])%mod;if(x!=1)// 左括号不能染1f[i][j][1][0]=(f[i][j][1][0]+f[i+1][j-1][x][y])%mod;if(x!=2)// 左括号不能染2f[i][j][2][0]=(f[i][j][2][0]+f[i+1][j-1][x][y])%mod;}}else// i和j不匹配{intk=match[i];// i的匹配位置for(intx=0;x<=2;x++)for(inty=0;y<=2;y++)for(intp=0;p<=2;p++)for(intq=0;q<=2;q++){// 枚举四个端点的颜色if((p==1&&q==1)||(p==2&&q==2))// 相邻颜色不能相同continue;f[i][j][x][y]=(f[i][j][x][y]+f[i][k][x][p]*f[k+1][j][q][y]%mod)%mod;}}}// 统计答案for(inti=0;i<=2;i++)for(intj=0;j<=2;j++)ans=(ans+f[1][n][i][j])%mod;// 累加所有染色方案cout<<ans<<endl;// 输出答案return0;}