求字符串的子序列问题(语言-c++)

Question

题目描述

众所周知，珂朵莉是世界上最幸福的女孩子；
但这道题目与幸福没有任何关系；
珂朵莉发现，对于任何一个字符串s都有一个珂学值，即其中含有子序列“chtholly”的个数
由于珂学崇尚壮阔，珂学值的结果可能很大

输入

第1行一个字符串S。

输出

共1行，一个整数，表示珂学值

提示

对于10%的数据，|S|<=8
对于30%的数据，|S|<=20
对于60%的数据，|S|<=1000
对于100%的数据，|S|<=100000
答案保证在可输出的范围内

我感觉应该是用dp 就写了一下
但是代码卡在60分过不去了 显示答案错误 请指教一下哪里出了问题QAQ

#include<bits/stdc++.h>
using namespace std;
string k={"chtholly"};
long long  f[100005][13];
char ch[100005];
int main()
{
   scanf("%s",&ch);
   int n=strlen(ch);
   for(int i=0;i<n;i++)
   {
        for(int j=0;j<=7;j++)
        {
            f[i+1][j+1]=f[i][j+1];

            if(k[j]==ch[i])
            {
            if(j==0)f[i+1][j+1]++;
            else
            f[i+1][j+1]+=f[i][j];

            }
        }
   }

   cout<<f[n][8];
    return 0;
}

ok啦！

#include<bits/stdc++.h>
using namespace std;
string k={"chtholly"};
string sum[8]={"0","0","0","0","0","0","0","0"};
char ch[200005];
string add(string  n,string  m)
{
   string x;
   int a=n.size(),b=m.size();
   int mins=min(a,b),temp=0,i;
   for( i=0;i<mins;i++)
   {
       int s=(int)n[i]+(int)m[i]-48*2+temp;
       if(s>9)temp=1;
       else temp=0;
       x+=(char)(s%10+48);
       //cout<<i<<" ";
   }
   while(i<a)
   {
       int s=(int)n[i++]-48+temp;
       if(s>9)temp=1;
       else temp=0;
       x+=(char)(s%10+48);
       // cout<<i<<" ";
   }
     while(i<b)
   {
       int s=(int)m[i++]-48+temp;
       if(s>9)temp=1;
       else temp=0;
       x+=(char)(s%10+48);
       // cout<<i<<" ";
   }
   if(temp)x+='1';
   //cout<<x<<endl;

    return x;
}
int main()
{
   scanf("%s",ch);
   int n=strlen(ch);
    string u="1";
   for(int i=0;i<n;i++)
   {
       if(ch[i]=='c')sum[0]=add(sum[0],u);
       for(int j=7;j>=1;j--)
       {
           if(ch[i]==k[j])sum[j]=add(sum[j-1],sum[j]);
       }

   }
    for(int i=sum[7].size()-1;i>=0;i--)cout<<sum[7][i];
    return 0;
}

Answer 1

vector<int>f[10];
vector<int> add(vector<int> &A, vector<int> &B)
{
    if (A.size() < B.size()) return add(B, A);
 
    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size(); i ++ )
    {
        t += A[i];
        if (i < B.size()) t += B[i];
        C.push_back(t % 10);
        t /= 10;
    }
 
    if (t) C.push_back(t);
    return C;
}
 
void solve(){
         
         string s;
         cin >> s;
         f[0].push_back(1);
         for(int i = 0 ; i < s.size() ; i ++ ){
             if(s[i] == 'c') f[1] = add(f[0],f[1]) ;
             if(s[i] == 'h') f[2] = add(f[1],f[2]) ;
             if(s[i] == 't') f[3] = add(f[2],f[3]) ;
             if(s[i] == 'h') f[4] = add(f[3],f[4]) ;
             if(s[i] == 'o') f[5] = add(f[4],f[5]) ;
             if(s[i] == 'l') f[7] = add(f[7],f[6]) ;
             if(s[i] == 'l') f[6] = add(f[6],f[5]) ;
             if(s[i] == 'y') f[8] = add(f[8],f[7]);
              
         }
         reverse(f[8].begin(),f[8].end());
         for(auto i : f[8]) cout<<i;
          
}