DP训练 CDOJ1321柱爷的恋爱 [区间dp]

xiaoxiao2021-02-28  25

此题原本为我下午准备讲课的题,居然。。。10分钟ac

这运气。。。果真我cdoj做多了。

括号匹配 (parenthesis.pas/cpp/c)

【题目描述】 给出长度为N的括号序列(只包含(,),[,]),问有多少种方法删掉这些括号的一个子集,使得剩下的括号序列是合法的,请注意不能全部删完。 【输入格式】 输入的第一行是一个整数N,表示序列的长度。 接下来一行N个字符,表示括号序列。 【输出格式】 一行,表示方案数模1000000007的结果。 【样例输入】 4 ()[] 【样例输出】 3 【数据范围】 30%的数据保证:1 <= N <= 20。 100%的数据保证:1 <= N <= 300。

思考

裸的区间DP, 1.当 i==j dp[i][j]=1 ; 2当i!=j&&i,k为一对匹配括号, dp[i][j]=res+dp[i+1][k1]+dp[k+1][j] ; 3其他情况 dp[i][j]=dp[i+1][j] ;

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; char s[305]; long long dp[305][305]; long long dfs(long long i,long long j){ if(dp[i][j]>=0)return dp[i][j]; if(i>=j)return 1; long long res=dfs(i+1,j); char rt='0'; if(s[i]=='(')rt=')'; else if(s[i]=='[')rt=']'; if(rt!='0') for(long long q=i+1;q<=j;q++)if(s[q]==rt) res=max(res,res+dfs(i+1,q-1) *dfs(q+1,j))%1000000007; dp[i][j]=res; return res%1000000007; } int main(){ // freopen("parenthesis.in","r",stdin); // freopen("parenthesis.out","w",stdout); long long n; cin>>n; for(register long long i=0;i<=n;i++) for(register long long j=0;j<=n;j++)dp[i][j]=-1; cin>>s; long long ans=((dfs(0,n-1)%1000000007-1)%1000000007+1000000007)%1000000007; cout<<ans<<endl; return 0; } //
转载请注明原文地址: https://www.6miu.com/read-1450029.html

最新回复(0)