NC21814. 筱玛的字符串
描述
输入描述
一行一个字符串S。
输出描述
一行一个整数，表示模意义下的答案。
示例1
输入:
??))
输出:
7
说明:
()(),()))C++14(g++5.4) 解法, 执行用时: 194ms, 内存消耗: 118248K, 提交时间: 2019-01-11 19:51:22
#include<bits/stdc++.h>
#define maxn 3010
#define ll long long
using namespace std;
int n;
ll f[maxn][maxn][3];
const ll p=1e9+7;
char s[maxn];
int main()
{
scanf("%s",s+1),n=strlen(s+1);
f[0][0][0]=1;
for(int i=1;i<=n;i++)
{
for(int j=0;j<=i;j++)
{
if(s[i]!='(')
{
f[i][j][0]+=f[i-1][j+1][0];
if(j)
f[i][j][1]+=f[i-1][j-1][0]+f[i-1][j-1][1];
f[i][j][2]+=f[i-1][j+1][1]+f[i-1][j+1][2];
}
if(s[i]!=')')
{
if(j)
f[i][j][0]+=f[i-1][j-1][0];
f[i][j][1]+=f[i-1][j+1][0]+f[i-1][j+1][1];
if(j)
f[i][j][2]+=f[i-1][j-1][1]+f[i-1][j-1][2];
}
for(int k=0;k<3;k++)
f[i][j][k]%=p;
}
}
printf("%lld\n",(f[n][0][0]+f[n][0][1]+f[n][0][2])%p);
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 134ms, 内存消耗: 118252K, 提交时间: 2019-01-11 19:40:23
#include<bits/stdc++.h>
#define maxn 3010
#define ll long long
using namespace std;
int n;
ll f[maxn][maxn][3];
const ll p=1e9+7;
char s[maxn];
int main(){
scanf("%s",s+1),n=strlen(s+1);
f[0][0][0]=1;
for(int i=1;i<=n;i++){
for(int j=0;j<=i;j++){
if(s[i]!='('){
f[i][j][0]+=f[i-1][j+1][0];
if(j)
f[i][j][1]+=f[i-1][j-1][0]+f[i-1][j-1][1];
f[i][j][2]+=f[i-1][j+1][1]+f[i-1][j+1][2];
}
if(s[i]!=')'){
if(j)
f[i][j][0]+=f[i-1][j-1][0];
f[i][j][1]+=f[i-1][j+1][0]+f[i-1][j+1][1];
if(j)
f[i][j][2]+=f[i-1][j-1][1]+f[i-1][j-1][2];
}
for(int k=0;k<3;k++)
f[i][j][k]%=p;
}
}
printf("%lld\n",(f[n][0][0]+f[n][0][1]+f[n][0][2])%p);
return 0;
}