题意:给出一个字符串,字符串只包含了(,),?三种字符,而?可以变成()两种字符,问所有能产生的字符串中的所有深度和
深度的意义表示为: ()这样就有一层深度,贡献为1, (())这样就有两层,贡献为2,()()这样只有一层,贡献也为1
样例:(?(?)) 这组样例输出 9
具体表现为
(((()) 深度为2
()()))深度为2
((())) 深度为3
()(()) 深度为2
所以总贡献就是2+2+3+2=9
solve:
根据官方题解来说,其实就是个区间dp
让两个指针位于序列的每个末端。
如果左指针的字符是')',我们将左指针向右移动一个位置。
如果右指针处的字符是'(',我们将右指针向左移动一个位置。
如果左指针处的字符为'(',右指针为')',我们将增加结果,并将左指针向右移动,右指针向左移动一个位置。
设f[i][j]表示从i~j中的贡献是多少
之后分情况讨论
对于当前的i,j位置 如果a[i]不是个左括号,直接加f[i+1][j]的值就行了(此时相当于不考虑当前i位置的贡献)
如果a[j]不是个右括号,直接继续加上f[i][j-1]就行了(同理)
而这样做完,如果a[i]!='('&&a[j]!=')'那么根据我们上面两个操作,其实我们加多了个f[i+1][j-1]的,我们把他减回去!!!
如果我们当前a[i]!=')'&&a[j]!='('那么这个地方就有贡献,因为如果是这种情况,端点处的位置不是?就是正确的左右括号,那么我们直接加上f[i+1][j-1]产生的贡献
跟2^k(k表示i+1~j-1区间?的个数)
为什么要加这个呢?f[i+1][j-1]表示的是不用最外面的括号产生的贡献,那么如果用了就相当于给所有情况的加上了1,而这里的所有情况就是2^k
#include <bits/stdc++.h> using namespace std; #define ll long long #define re register const int mod=998244353; void read(int &a) { a=0;int d=1;char ch; while(ch=getchar(),ch>'9'||ch<'0') if(ch=='-') d=-1; a=ch^48; while(ch=getchar(),ch>='0'&&ch<='9') a=(a<<3)+(a<<1)+(ch^48); a*=d; } ll f[2005][2005]; int p[2005]; char a[2005]; int quickmod(int x,int y) { int res=1,base=x; while(y) { if(y&1) res=1ll*res*base%mod; base=1ll*base*base%mod; y>>=1; } return res; } int main() { scanf("%s",a); int len=strlen(a); for(re int i=0;i<len;i++) p[i+1]=p[i],p[i+1]+=a[i]=='?'; for(re int t=2;t<=len;t++) { for(re int i=0;i<len-t+1;i++) { int j=i+t-1; if(a[i]!='(') (f[i][j]+=f[i+1][j])%=mod; if(a[j]!=')') (f[i][j]+=f[i][j-1])%=mod; if(a[i]!='('&&a[j]!=')') f[i][j]=(f[i][j]-f[i+1][j-1]+mod)%mod; if(a[i]!=')'&&a[j]!='(') f[i][j]=(f[i][j]+f[i+1][j-1]+quickmod(2,p[j]-p[i+1]))%mod; } } printf("%lld",f[0][len-1]); return 0; }