众所周知，珂朵莉是世界上最幸福的女孩子；
但这道题目与幸福没有任何关系；
珂朵莉发现，对于任何一个字符串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;
}
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;
}
修改如下：
#include<bits/stdc++.h>
using namespace std;
string k={"chtholly"};
long long f[100005][13]={0}; //这里初始化一下
char ch[100005];
int main()
{
scanf("%s",&ch);
int n=strlen(ch);
for(int i=0;i<n-1;i++)//这里改成 i<n-1
{
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;
}