首页 > 其他分享 >CF1015F 题解

CF1015F 题解

时间:2024-07-25 16:19:27浏览次数:12  
标签:gets 匹配 CF1015F int 题解 括号 aligned dp

题面

考虑这样的匹配问题,可以想如何确定第一次匹配,这样可以不重不漏地计数。

考虑 dp 的时候同时维护有几个括号没有匹配,匹配到 \(s\) 的第几位,所以令 \(f(i,j,k)\) 表示 dp 到(要计数的序列的)第 \(i\) 个字符,有 \(j\) 个左括号没有匹配,匹配到 \(s\) 的第 \(k\) 位。

转移很容易,考虑对每个 \(i,j\) 和 \(k(k<|s|)\),有两种转移(刷表法):

\[\begin{aligned} &f(i+1,j+1,to_{k,0}) \gets f(i,j,k)\quad (s_{i+1}=\texttt{(}) \\ &f(i+1,j-1,to_{k,1}) \gets f(i,j,k)\quad (s_{i+1}=\texttt{)}) \end{aligned} \]

初始值为 \(f(0,0,0)=1\)。

其中 \(to_{k,0/1}\) 为当匹配到 \(s\) 的第 \(k\) 位时,下一位分别为两种括号的最长匹配,求法有两种:kmp 跳失配指针 或者 直接字符串比较暴力求。

对答案有贡献的即为 \(f(i,j,m)\),但是后面还有 \(2n-i\) 位没有确定,这时只需要乘上 右括号比左括号多 \(j\) 个且每个左括号都能匹配的括号序列个数即可,可以用卡特兰数,也可以直接 dp。

考虑 dp:设 \(g_{i,j}\) 为右括号比左括号多几个,显然 \(j\geq 0\),转移为:

\[\begin{aligned} &g(i+1,j+1) \gets g(i,j) \\ &g(i+1,j-1) \gets g(i,j) (j\geq 0) \end{aligned} \]

初始值为 \(g(0,0)=1\)。

总复杂度瓶颈在 \(f\) 的 dp 上,为 \(O(n^3)\)。


#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 205, p = 1e9 + 7;
int f[N][N][N], g[N][N], to[N][2], n;
char s[N];

bool eq(int len, int x, int y)
{
    for(int i = x, j = y; i < x + len; i ++, j ++)
        if(s[i] != s[j]) return 0;
    return 1;
}

signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    cin >> n >> s + 1;
    int m = strlen(s + 1);
    for(int i = 0; i < m; i ++)
    for(int j = 0; j <= i; j ++)
    for(int k : {0, 1})
        if(s[j + 1] == k + 40 && eq(j, 1, i - j + 1))
            to[i][k] = j + 1;
    g[0][0] = 1;
    for(int i = 0; i < n * 2; i ++)
    for(int j = 0; j <= n; j ++)
    {
        g[i + 1][j + 1] = (g[i + 1][j + 1] + g[i][j]) % p;
        if(j) g[i + 1][j - 1] = (g[i + 1][j - 1] + g[i][j]) % p;
    }
    f[0][0][0] = 1;
    for(int i = 0; i < n * 2; i ++)
    for(int j = 0; j <= n; j ++)
    for(int k = 0; k < m; k ++)
    for(int u : {0, 1})
    {
        int c = u ? -1 : 1;
        if(j + c >= 0) f[i + 1][j + c][to[k][u]] = (f[i + 1][j + c][to[k][u]] + f[i][j][k]) % p;
    }
    int ans = 0;
    for(int i = 1; i <= n * 2; i ++)
    for(int j = 0; j <= n; j ++)
        ans = (ans + 1ll * g[n * 2 - i][j] * f[i][j][m]) % p;
    cout << ans;

    return 0;
}

标签:gets,匹配,CF1015F,int,题解,括号,aligned,dp
From: https://www.cnblogs.com/adam01/p/18323461

相关文章

  • 程序设计:C++入门教程(速成) + 15道经典例题(附带例题解析)
    本文章以实用为主,若实在是不明白文字所表达的内容,无脑复制代码,自己动手运行一下,实验一下即可理解文章内容,放心,代码是全的,全选复制粘贴即可不废话,直接开整数据类型常用数据类型int:整数类型,用于表示整数值。例如:1,2,-3,0等。float:单精度浮点数类型,用于表示带有小数点的数......
  • AT_arc116_e [ARC116E] Spread of Information 题解
    题目传送门前置知识二分答案|树形DP解法答案显然具有单调性,考虑二分答案。设当前二分出的答案为\(mid\),则等价于覆盖距离为\(mid\)的情况下进行选点。做法同luoguP3942将军令,考虑进行贪心,对于深度最深的叶节点将选择的点放在边界时,即取\(mid\)级祖先时,覆盖的范......
  • 题解—[ABC265E] Warp
    题面简单计数DP。由于数据范围很大,所以状态不能常规设置为\(dp_{i,j}\)。注意到\(n\)只有\(300\),考虑设\(dp_{i,j,k}\)表示三种行走方法分别使用\(i\),\(j\),\(k\)次的路径数量。状态转移很简单,先计算出来当前所在位置,如果是障碍就跳过,否则$dp_{i,j,k}=dp_{i-1,j,k}+dp......
  • P2671 [NOIP2015 普及组] 求和 题解
    题目:P2671NOIP2015普及组求和题意给定一个带有颜色和数字的序列,我们要寻找三元组\((x,y,z)\)满足以下条件:\(y\)为\(x\)和\(z\)的中点且都为整数。\(color[x]=color[z]\)。我们命这样一个三元组对答案的贡献为\((x+z)*(num[x]+num[z])\)。整个序列的总价值为每个......
  • Temperature 题解
    前言题目链接:洛谷;SPOJ;Hydro&bzoj。题意简述有一个长度为\(n\)的序列,每个位置值的范围为\([L_i,R_i]\)内,求原序列可能的最长不降子串长度。题目分析尝试找一些性质。发现,连续一段合法的区间,都能分成若干真正参与最长不降子串,以及紧跟着的若干包含\(L_i\)的位置。下图......
  • [ABC318E]Sandwiches 题解
    题意给定一个序列\(A\),要求找有多少个三元组\((i,j,k)\)满足以下条件:\(1\lei<j<k\leN\)\(A_i=A_k\)\(A_i\neA_j\)思路相当于是找每两个相同的元素中有多少个不同的数字。例如:12131答案显然是4,即是\((1,2,3)(1,2,5)(1,4,5)(3,4,5)\)。用\(q[A[i]]\)......
  • [题解]CF117C Cycle
    思路发现最简单的方法就是直接枚举三个点,但是复杂度\(\Theta(n^3)\)无法接受。考虑枚举一个点,并确定它的一条边,那么只需要再枚举一个点了。于是转化为了,对于每一个点找到其最好的出边。观察下图,\(a\toc\)的边是不必要的。因为,如果有一个三元环包含\(a\toc\),那么一定能......
  • P3294 [SCOI2016] 背单词 题解
    题意给你\(n\)个字符串,让你对其进行排列,使得按以下规则花费最少:设当前字符串为\(s\),\(x\)为\(s\)在答案排列中的位置。如果\(s\)存在后缀且\(s\)的后缀在\(s\)之后,花费加\(n^2\)。如果\(s\)不存在后缀则花费加\(x\)。设\(y\)为\(s\)之前离其最近的......
  • P10717 题解
    好神仙的题目。赛时胡了一个状态和转移都和官解不同的做法,得到了\(O(n10^m)\)的优秀复杂度。卡了一场常卡进了\(75\)分。这个做法和官解关系不大,并且很难进行最后的优化部分,所以在此不再赘述。首先考虑\(k=1\)的情况。考虑记录一些状态能够描述子树内的选择方案,\(0\)表示......
  • 题解:Codeforces Round 961 (Div. 2) A
    A.Diagonals*timelimitpertest:1secondmemorylimitpertest:256megabytesinput:standardinputoutput:standardoutputVitaly503isgivenacheckeredboardwithasideof\(n\)and\(k\)chips.Herealizedthatallthese\(k\)chipsneedto......