题目描述
递变是指通过增加、减少或改变单词x中的一个字母，使它变成字典中的另一个单词y。比如将dig变成dog，将dog变成do都是递变。递变阶梯是一个按字典序排列的单词序列w1,w2,...wn，满足对于从1到n-1的所有i，单词wi到wi+1都是一次递变。相同的单词之间不能递变。n=15000
给出一部字典，你要计算其中最长的递变阶梯。
题目分析
容易看出这是一个DAG的最长路(类似LIS),那么我们可以想到一个O(n^2)的算法,显然超时.
换个方式想,如果我们枚举每个字符串可以变成的另一个字符串,再判断是否在里面,那么容易发现不会超时(15000*16*26),那么我们可以这样建图,然后走DAG最长路,很可惜我下面这份代码由于Hash的特殊性,无法通过Uva,仅能通过Codevs
题目代码
#include<bits/stdc++.h>
using namespace std;
string str[];
const int base = ;
typedef unsigned long long ull;
ull f[][];
ull base_pow[],ans[];
ull num[],pla[];
ull mod = ; int main(){
int n=;
while(cin>>str[++n])if(str[n]==str[n-])n--;
n--;
base_pow[]=;
for(int i=;i<=;i++)base_pow[i]=base_pow[i-]*base;
for(int i=;i<=n;i++){
f[i][]=str[i][]-'a'+;
for(int j=;j<str[i].length();j++)
f[i][j]=f[i][j-]*base+str[i][j]-'a'+;
num[f[i][str[i].length()-]%mod]=;
pla[f[i][str[i].length()-]%mod]=i;
}
for(int i=;i<=n;i++)ans[i]=;
for(int i=;i<=n;i++){
string s=str[i];
for(int j=;j<s.length();j++){
ull sd = f[i][s.length()-];
sd-=f[i][j]*base_pow[s.length()-j-];
if(j->=)
sd+=f[i][j-]*base_pow[s.length()-j-];
if(num[sd%mod]&&pla[sd%mod]<i&&s.length()->)
ans[i]=max(ans[i],ans[pla[sd%mod]]+);
}
for(int j=;j<s.length();j++){
ull sd = f[i][s.length()-];
sd-=f[i][j]*base_pow[s.length()-j-];
if(j->=)
sd+=f[i][j-]*base_pow[s.length()-j-];
if(num[sd%mod]&&pla[sd%mod]>i&&s.length()->)
ans[pla[sd%mod]]=max(ans[pla[sd%mod]],ans[i]+);
}
for(int j=;j<str[i].length();j++){
ull sd;
for(int k=;k<=;k++){
sd = f[i][s.length()-];
sd-=f[i][j]*base_pow[s.length()-j-];
sd+=k*base_pow[s.length()-j-];
if(j->=)
sd+=f[i][j-]*base_pow[s.length()-j];
if(num[sd%mod]&&pla[sd%mod]>i)
ans[pla[sd%mod]]=max(ans[pla[sd%mod]],ans[i]+);
}
}
}
ull maxx=;
for(int i=;i<=n;i++){
maxx=max(maxx,ans[i]);
}
cout<<maxx;
}