题目背景

T1答案要mod1000000007(10^9+7)，请重新提交，非常抱歉！

一天，智障的pipapi正在看某辣鸡讲义学程序设计。

题目描述

在讲义的某一面，他看见了一篇文章。这篇文章由英文字母（大小写均有）、数字、和空白字符（制表/空格/回车）构成。

pipapi想起了他最近刚刚学会写的Hello World程序。他非常好奇，这篇文章中，“HelloWorld”作为子序列到底出现过多少次呢？

由于papapi是个智障，大小写对于他而言毫无区别；因此，“hEllOWorLD”这样的子序列也是可以接受的。O和W之间的空格是也是可以少的；也就是说，“HelloWorld”是可以的。根据标程的意思，就是没有空格，不用考虑空格的情况。

两个子序列相同当且仅当它们每一个字符所在的位置都相同。

由于答案可能很大，请输出结果对1000000007(10^9+7)的余数。

输入输出格式

输入格式：

输入包含若干行。这些行的内容共同构成一篇文章。

文章以EOF（文件结尾）结束。

输出格式：

输出仅包含一个整数，表示这篇文章中“Hello World”出现的次数。

输入输出样例

输入样例#1：

HhEeLlLlOoWwOoRrLlDd

输出样例#1：

输入样例#2：

Gou Li Guo Jia Sheng Si Yi

Qi Yin Huo Fu Bi Qu Zhi

River can feed people

Also can race boats

Hall Ellen Ok Words locked

输出样例#2：

说明

记n为输入的文章的长度（字符数）。

对于20%的数据，n <= 20。

对于50%的数据，n <= 500。

对于所有的数据，15 <= n <= 500000。

　　一道比较裸的dp题，把Helloworld拆成11个状态，"","h","he","hel"以此内推。处理文章。过滤掉所有没有用的字符，重新组成字符串。

用f[i][j]表示从第1个字符到第i个字符达到第j个状态的方案数。于是可以轻松地得出状态转移方程f[i][j] = f[i - 1][j] + （page[i] == sets[i]）? (f[i - 1][j - 1]) : (0)(page表示处理后的文本串，sets[i]表示"helloworld"的第i个字符)。注意初值，在任何位置，组成空字符串的方案只有一种，所以f[i][0] = 1

Code

 /**

  * luogu.org

  * Problem#2246

  * Accepted

  * Time:507ms

  * Memory:17121k

  */

 #include<iostream>

 #include<cstdio>

 #include<cctype>

 #include<cstring>

 #include<cstdlib>

 #include<fstream>

 #include<sstream>

 #include<algorithm>

 #include<map>

 #include<set>

 #include<queue>

 #include<vector>

 #include<stack>

 using namespace std;

 typedef bool boolean;

 #define INF 0xfffffff

 #define smin(a, b) a = min(a, b)

 #define smax(a, b) a = max(a, b)

 #define moder 1000000007

 template<typename T>class Matrix{

     public:

         T *p;

         int lines;

         int rows;

         Matrix():p(NULL){    }

         Matrix(int rows, int lines):lines(lines), rows(rows){

             p = new T[(lines * rows)];

         }

         T* operator [](int pos){

             return (p + pos * lines);

         }

 };

 #define matset(m, i, s) memset((m).p, (i), (s) * (m).lines * (m).rows)

 int n;

 Matrix<int> f;

 char page[];

 inline void init(){

     char x;

     while(~(x = getchar())){

         if(x == 'h' || x == 'H')    page[++n] ='h';

         else if(x == 'e' || x == 'E')    page[++n] = 'e';

         else if(x == 'l' || x == 'L')    page[++n] = 'l';

         else if(x == 'o' || x == 'O')    page[++n] = 'o';

         else if(x == 'w' || x == 'W')    page[++n] = 'w';

         else if(x == 'r' || x == 'R')    page[++n] = 'r';

         else if(x == 'd' || x == 'D')    page[++n] = 'd';

     }

     f = Matrix<int>(n + , );

     matset(f, , sizeof(int));

 }

 char sets[] = " helloworld";

 inline void solve(){

     for(int i = ; i <= n; i++)    f[i][] = ;

     for(int i = ; i <= n; i++){

         for(int j = ; j > ; j--){

             (f[i][j] += f[i - ][j]) %= moder;

             if(page[i] == sets[j])    (f[i][j] += f[i - ][j - ]) %= moder;

         }

     }

     printf("%d", f[n][]);

 }

 int main(){

     init();

     solve();

     return ;

 }

Sets

洛谷月赛 Hello World（升级版） - 动态规划