2846. 统计字符串个数

10175102262 LarsPendragon

动态规划。
思路:f(n)=f(n-1)+(f(n-1)-f(n-2)+f(n-3))。解释:长度为n的不含101的字串有2种可能:第一,长度为n-1的不含101的字串结尾+0;第二:长度为n-1的不含101的字串结尾+1。但第二种情况应除去结尾是101的字串。具体操作为减去结尾为01的字串再加上结尾为001的字串。

#include <iostream>
using namespace std;
int main()
{
    int m, n[21]={0};
    n[1]=2;
    n[2]=4;
    n[3]=7;
    for(int i=4; i<21; i++) n[i]=2*n[i-1]-n[i-2]+n[i-3];
    cin>>m;
    while(m+1){cout<<n[m]<<endl;cin>>m;}
    return 0;
}
10175101290

为什么不直接减去结尾为101的子串呢

NAN

因为,如果用f(n-3)表示长度为n-3不含101的字符串。f(n-3)里包括末尾是“10”的情况,它并不在f(n-1)里,不能用它直接减。

Saitama

感谢讲解

Deuchie

设 $a[n]$ 是以 $0$ 结尾的不含 $101$ 的长为 $n$ 的字符串的个数,$b[n]$ 是以 $1$ 结尾的不含 $101$ 的长为 $n$ 的字符串的个数。

Base Case:

$$
a[0] = b[0] = 0, \
a[1] = b[1] = 1.
$$
对 $a$ 而言,有 $a[n] = a[n-1]+b[n-1]$;即:长为 $n - 1$ 的不含 $101$ 的字符串后再加一个 $0$。

对 $b$ 而言,有 $b[n] = (b[n-1]) + (a[n-1] - b[n-2])$;即:长为 $n - 1$ 的不含 $101$ 的也不以 $10$ 结尾的字符串后再加一个 $1$。

由此可以得到公式:
$$
a[n] = a[n-1]+b[n-1];\
b[n] = a[n] - b[n-2];
$$
代码:

int main() {
    uint32_t a[21], b[21];
    a[0] = b[0] = 0, a[1] = b[1] = 1;
    for (uint32_t i = 2; i <= 20; ++i)
        a[i] = a[i - 1] + b[i - 1],
        b[i] = a[i] - b[i - 2];
    for (int n; std::cin >> n, n != -1;)
        printf("%u\n", a[n] + b[n]);
}
桑榆非晚

这个数学公式是用latex吗?

Deuchie

嗯,用 LaTex 的语法就行

10175101134

感谢讲解

你当前正在回复 博客/题目
存在问题!