题解 P2246 【SAC#1 - Hello World（升级版）】

· · 题解

啊啊啊，终于AC了……心好累……

这题很明显是DP，因为它满足DP的两个性质——最优子结构、无后效性。（不知道这些的请回去看看DP吧）（划掉）

状态很明显：考虑文本串前i个字符匹配模板前j个字符的匹配数。

转移也很明显：当第i个字符是文本中的第j个，dp[i][j]=dp[i-1][j]+dp[i-1][j-1]，其他dp[i][j]=dp[i-1][j]（因为这个字符对于匹配没有用嘛）

现在只差一个：边界。

//众：我倒！！！

边界是什么呢？我们知道dp[0][i]=0，但dp[i][0]是几呢？在文本中匹配一个空串？晕。。。

看看样例吧：

HhEeLlLlOoWwOoRrLlDd

现在，我们在文本前加一个奇gay的字符，比如♂【滑稽】

那么文本就变成了：

♂HhEeLlLlOoWwOoRrLlDd

让我们把♂看成模板（即“helloworld”）的第0个字符。这个时候，边界明显了吧。。。

还有一个细节：模板中有重复字符，因此要逆序循环，不然会WA（考虑一下“hhhhhhh”这个模板就明白了）

代码：

#include <iostream>
#include <cstdio>
using namespace std;
const int mod=1000000007;
int main()
{
    long long dp[11]={1};
    char c,hello[20]="?helloworld";
    while((c=getchar())!=EOF)
    {
        for(int i=10;i>=1;i--)if(c==hello[i]||c+32==hello[i])dp[i]=(dp[i-1]+dp[i])%mod;
    }
    cout<<dp[10];
    return 0;
}