codevs2019 Uva10029 递变阶梯

题目描述

递变是指通过增加、减少或改变单词x中的一个字母，使它变成字典中的另一个单词y。比如将dig变成dog，将dog变成do都是递变。递变阶梯是一个按字典序排列的单词序列w₁,w₂,...w_n，满足对于从1到n-1的所有i，单词w_i到w_i+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;

 }

巴特西

codevs2019 Uva10029 递变阶梯

最新文章

热门文章