Game TJ （含另类思路）
题意：
-
给定 $ N $ 个按长度排序的单词。
-
规定接龙的规则为：若 $ t $ 是 $ s $ 的真前缀，则 $ s $ 可以接龙在 $ t $ 后面。
-
求最多接龙次数。
-
$ N \leq 50000 $，对于每个字符串 $ s $，满足 $ length ( s ) \leq 50$
思路：
两种思路，先介绍一个正常的：
首先我们不管原来的顺序，按字典序排列，此时可以保证又相同前缀的字符串排在一起。
那么就可以维护一个栈，依次扫描字符串，若栈顶为空，直接入栈，否则弹出不为当前字符真前缀的栈顶，再用栈顶更新接龙次数，然后扔进去更新答案。
时间复杂度为 $ O ( N \log N) $ 级别，实际可能更慢，其主要瓶颈在排序。
这个解法考虑了接龙的实际要求，并利用了栈后进先出的特点，保障了正确性。
第二种解法是我自己想的，思路如下：
考虑一个字符串 $ s $，它只能在比他短的单词后接龙。
那么对于长度的排序是由一定意义的。
简单的想法是对于每个字符串，枚举前面能用来更新它的字符串，取最大值进行更新。可以证明，这样做不存在后效性。
然而这样的时间可能会达到 $ O ( N ^ 2 ) $，不能接受。
注意到字符串长度仅有 $ 50 $，直接检索前缀不会超时。那么可以建立一个字典树，在检索字符串的过程中，就可以查找出最大的可以用来更新他的字符串。
该解法时间复杂度为 $ O ( N C ) $，很好地利用了原来给出的顺序。
那么在这里给出我第二种解法的代码：
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
typedef long long ll;
namespace OI{
template<class T> inline T min(const T x,const T y){
return x<y?x:y;
}
template<class T> inline T max(const T x,const T y){
return y<x?x:y;
}
template<class T> inline T abs(const T x){
return x<0?-x:x;
}
template<class T> inline void swap(T x,T y){
T tmp=x;
x=y,y=tmp;
}
const int MAXSIZE=1048576;
char buf[MAXSIZE], *p1, *p2;
// #define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXSIZE,stdin),p1==p2)?EOF:*p1++)
#define gc() getchar()
template<class T> inline T read(){
T x=0;register bool f=1;register char ch=gc();
while('0'>ch||'9'<ch){if(ch=='-')f=0;ch=gc();}
while('0'<=ch&&'9'>=ch)x=(x<<3)+(x<<1)+(ch^48),ch=gc();
return f?x:-x;
}
// char pbuf[1<<20],*pp=pbuf;
// inline void pc(const char &c){
// if(pp-pbuf==1<<20) fwrite(pbuf,1,1<<20,stdout),pp=pbuf;
// *pp++=c;
// }
#define pc(x) putchar(x)
template<class T>inline void write(T x){
if(x<0) pc('-'),x=-x;
static int sta[35];
int top=0;
do sta[top++]=x%10,x/=10;
while(x);
while(top) pc(sta[--top]^48);
}
};
using namespace OI;
int dp[50005];
int t[MAXSIZE][30],tot;
int c[MAXSIZE];
inline void insert(string s,int num){
int p=0;
for(int i=0;i<s.length();i++){
int now=s[i]-'a';
if(!t[p][now]) t[p][now]=++tot;
p=t[p][now];
}
c[p]=num;//检索，存入dp的值
}
inline int ask(string s){
int p=0,num=0;
for(int i=0;i<s.length();i++){
int now=s[i]-'a';
if(!t[p][now]) return num;
p=t[p][now];
if(i!=s.length()-1) num=OI::max(num,c[p]);//除非是和自己相同，其他是自己前缀的都可以用来更新
}
return num;
}
signed main(){
int n=read<int>();
for(int i=1;i<=n;i++) dp[i]=1;
for(int i=1;i<=n;i++){
string s;
cin>>s;
dp[i]+=ask(s);
insert(s,dp[i]);
}
int ans=0;
for(int i=1;i<=n;i++) ans=OI::max(ans,dp[i]);//最后循环一遍得答案
write(ans);
return 0;
}
大概就是这么一个类似DP的过程。