如题,把排序改成字典序之后就过了(之前用的是以长度为第一关键字)。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
ll dp[55];
string a[55];
ll ans;
inline bool cmp(const string& a,const string& b){
// if(a.size()!=b.size())return a.size()<b.size();
return a<b;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++){
dp[i]=1;
for(int j=1;j<i;j++){
bool ok;
int sz1=a[i].size(),sz2=a[j].size();
if(sz1==sz2)ok=(a[i]!=a[j]);
else if(sz1>sz2)ok=(a[i].substr(0,sz2)!=a[j]);
else if(sz1<sz2)ok=(a[j].substr(0,sz1)!=a[i]);
// cout<<a[i]<<" "<<a[j]<<" "<<ok<<endl;
if(ok)dp[i]+=dp[j];
}
ans+=dp[i];
}
cout<<ans+1;
}