EOJ

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

动态规划

Posted by WeiYang on 2018-06-05

题目链接: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\)。

代码


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#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;
}