动态规划||记忆化搜索：Codeforces Round #597 (Div. 2)C. Constanze's Machine

C. Constanze's Machine

传送门:Problem - 1245C - Codeforces

题目：

题目大意：就是一个字符串，m 会变成nn w会变成uu 问一个字符串有原来有几种可能。显然如果出现m 或者 w直接输出0 不可能，否则可以用数学归纳法：

n:1种

nn:2种

nnn:3种

nnnn:5种

nnnnn:8种 

所以发现本质是fib数列，也就是斐波那契数列，则可以On的时间复杂度寻找连续的n和u有几个，然后记忆化搜索剪枝，把每个搜索结果*到ans上，ans初始化为1.

上代码：

 1 #include
 2 #include
 3 #include
 4 #include
 5 #include
 6 using namespace std;
 7 string s;
 8 long long dp[100000];
 9 const int mod = 1e9 + 7;
10 long long ans = 1;
11 int fib(int x)
12 {
13     if (dp[x])return dp[x];
14     else
15     {
16         dp[x] = fib(x - 1) + fib(x - 2);
17         dp[x] %= mod;
18         return dp[x];
19     }
20 }
21 int main()
22 {
23     cin >> s;
24     dp[1] = 1;
25     dp[2] = 2;
26     for (int i = 0; i < s.length(); ++i)
27     {
28         if (s[i] == 'u' || s[i] == 'n')
29         {
30             int x = 1;
31             int cnt = i;
32             i += 1;
33             while (i < s.length() && s[i] == s[cnt])
34             {
35                 x++;
36                 i++;
37             }
38             ans *= fib(x);
39             ans %= mod;
40             i--;
41         }
42         if (s[i] == 'w' || s[i] == 'm')
43         {
44             cout << "0";
45             return 0;
46         }
47     }
48     cout << ans;
49     return 0;
50 
51 }
动态规划搜索

相关

力扣530题（二叉搜索树的最小绝对差）

快速排序与随机构建二叉搜索树

PyCharm2021使用教程 ---9、PyCharm中的搜索技巧（文件/函数/内容）

动态规划-------最短路径问题

广度优先搜索复习笔记

无人机视觉导航搜索资料

背包问题c++动态规划方式

find 语句过滤掉某个目录搜索

Linux搜索指定目录中所有文件的内容

二分搜索的变形

MySQL（三）用正则表达式搜索

在 Spring Boot 中使用搜索引擎 Elasticsearch

标签