题目描述

此时相望不相闻，愿逐月华流照君。

一纸情书，到底蕴含了多少倍的爱情呢？

I love you, not only for what you are, but for what I am when I am with you.

输入描述:

共一行：一封若干个字符的情书（大小写不敏感）。
情书不会超过684594个字符（大写、小写字母）。

输出描述:

共一行：包含一个整数，即iloveyou在情书中作为子序列出现的次数。
由于答案可能很大，请输出对20010905取模后的值。

示例1

输入

IloveyouNotonlyforwhatyouareButforwhatIamWhenIamwithyouIloveyouNotonlyforwhatYouhavemadeofyourselfButforwhatYouaremakingofme

输出

2864

解题思路：线性dp，dp[i][j]表示前i个字符中包含目标字符中的前j个字符的子序列个数。

递推关系式：dp[i][j]=dp[i-1][j]%mod+(s[i]==目标字符)*dp[i-1][j-1]%mod

一定要注意取模运算！！！

#include<bits/stdc++.h>
using namespace std;
long long int dp[700000][10];int main()
{string s;getline(cin,s);int len=s.length();for(int i=0;i<len;i++){if(s[i]>='A'&&s[i]<='Z')s[i]+=32;}for(int i=1;i<=len;i++){dp[i][1]=dp[i-1][1]%20010905+(s[i-1]=='i')%20010905;dp[i][2]=dp[i-1][2]%20010905+(s[i-1]=='l')*dp[i-1][1]%20010905;dp[i][3]=dp[i-1][3]%20010905+(s[i-1]=='o')*dp[i-1][2]%20010905;dp[i][4]=dp[i-1][4]%20010905+(s[i-1]=='v')*dp[i-1][3]%20010905;dp[i][5]=dp[i-1][5]%20010905+(s[i-1]=='e')*dp[i-1][4]%20010905;dp[i][6]=dp[i-1][6]%20010905+(s[i-1]=='y')*dp[i-1][5]%20010905;dp[i][7]=dp[i-1][7]%20010905+(s[i-1]=='o')*dp[i-1][6]%20010905;dp[i][8]=dp[i-1][8]%20010905+(s[i-1]=='u')*dp[i-1][7]%20010905;}cout<<dp[len][8]%20010905;return 0;
}