EOJ2854. 统计特定字串模式的个数

题目链接:EOJ2854

题意


在0和1组成的长度为$n(1 \le n \le 31)$的字符串中,统计包含$m(1 \le m \le n)$个连续1子串的字符串的个数。

题解


这题要用到的算法思想是动态规划。

首先令$f(n, m)$表示长度为$n(1 \le n \le 31)$的字符串中,包含$m(1 \le m \le n)$个连续1子串的字符串的个数。考虑最后一位,也就是第$n$位的取值,可以分为两种情况:

  • 如果第$n$位为0,那么只能在前面的$n-1$位里取长度为$m$的连续1子串,那么答案就是
    \[f(n-1,m)\]
  • 如果第$n$位为1,那么考虑两种情况。
    一种是最后$m$位全为1,那么前面$n-m$位就可以任意取值,答案为
    \[2^{n-m}\]
    另一种情况是最后$m$位不全为1,也就是存在某一位为0,枚举最后一位0出现的位置,可能出现在第$n-1$位、第$n-2$位,一直到第$n-m+1$位,不管最后一个0出现在哪里,都要在之前的字符串中重新出现长度为$m$的连续1子串,所以答案是
    \[\sum\limits_{n - m \le i \le n - 2} {f(i,m)} \]

所以最终的答案就是
\[f(n,m) = {2^{n - m}} + \sum\limits_{n - m \le i \le n - 1} {f(i,m)} \]
进一步化简这个式子,用$n-1$替换$n$可以得到
\[f(n - 1,m) = {2^{n - m - 1}} + \sum\limits_{n - m - 1 \le i \le n - 2} {f(i,m)} \]
两式相减可以得到
\[f(n,m) = {2^{n - m - 1}} + 2f(n - 1,m) - f(n - m - 1,m)\]
边界条件为:

  • 当$n < m$时,$f(n,m)=0$。
  • 当$n = m$时,$f(n,m)=1$。

代码


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

int f(int n, int m) {
    if (n < m) return 0;
    if (n == m) return 1;
    int res = 2 * f(n - 1, m) - f(n - m - 1, m) + (1 << (n - m - 1));
    return res;
}

int main() {
    int n, m;
    while (scanf("%d%d", &n, &m) && (n != -1 || m != -1)) {
        int res = f(n, m);
        printf("%d\n", res);
    }
    return 0;
}

   转载规则


《EOJ2854. 统计特定字串模式的个数》 韦阳 采用 知识共享署名 4.0 国际许可协议 进行许可。
 上一篇
EOJ3006. 计算多项式的系数II EOJ3006. 计算多项式的系数II
题目链接:EOJ3006 题意 给定一个多项式${(ax + by)^k}$,计算多项式展开后${x^n}{y^m}$项的系数,结果对1000000007取模。 题解 由二项式定理可以得知,${x^n}{y^m}$项的系数就是\[{a^
2018-06-05
下一篇 
具体数学-第五章作业解答 具体数学-第五章作业解答
4. 题目:通过上指标翻转计算出$\left( {\begin{array}{*{20}{c}}{ - 1}\\k\end{array}} \right)$。解答:如果$k \ge 0$,那么\[\left( {\begin{array
2018-06-01
  目录