UVA - 10029 Edit Step Ladders

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=970
题意：
对于两个单词x和y，如果x可以通过删除、添加或者修改一个字母得到y，那么称为一次转换。
给出一个按字典序排列的字符串序列，求其中一个子序列，这个子序列的每一项可以由前一项转换而来，且该子序列是按字典序排列的，求子序列的最大长度。（表达能力欠佳。。就酱紫看吧）

思路：通过分析样例可以看出，只要按顺序对每一个转换建一条有向边（方向：i–>j，其中i< j ），然后求最大深度就ok辣
问题的难点就变成了怎样建边。如果暴力对每个字符串建边，显然O(n^2)会TLE。然后我有考虑按照长度分组，len之差<=1才有建边的可能，不过最差的情况也还是n^2。那如果预处理出每个字符串可能会转换到的情况呢？一开始想到这觉得那需要保存很多状态，其实不然，我们不必关心每次转换的具体字母是什么，只需要关心是否能转换得到就行了。所以我们大可不必将所有具体的情况列出来。
重点来啦：我们可以对每个字符串处理出他可能转换到的情况，而需要转换的字母可以用通配符来代替。这样对于修改，最多只有16种情况。而删除和增加，我们可以只考虑增加，因为x删除一个字母得到y，和y增加一个字母得到x是等价的。这样对于每个字符串，最多处理16+17次。

最长路的求解
设dp[i]=到i点为止题目所求子序列的最大长度
对于第i个字符串，如果它前面有一个字符串j能转换到它，那么对于该点
dp[i]=max(dp[i],dp[j]+1)

好啦，所有的问题都解决了，然后贴代码：

#include <bits/stdc++.h>
#define N 25005
using namespace std;
vector<string>strnum;
map<string,int>mp;
int dp[N];

string strChange(string str,int x){
    string src;
    for(int i=0;i<str.size();i++){
        if(i!=x)
            src.push_back(str[i]);
        else
            src.push_back('*');
    }
    return src;
}
string strAdd(string str,int x){
    string src;
    if(x==str.size()) {
        src = str + '*';
        return src;
    }
    for(int i=0;i<str.size();i++){
        if(i==x)
            src.push_back('*');
        src.push_back(str[i]);
    }
    return src;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    string str;
    while(getline(cin,str)){
        if(str.size()==0)
            break;
        strnum.push_back(str);
    }
    memset(dp,0, sizeof(dp));
    int ans=0;
    for(int i=0;i<strnum.size();i++){
        for(int j=0;j<strnum[i].size();j++){
            string src=strChange(strnum[i],j);
            if(mp.count(src)>0)
                dp[i]=max(dp[i],dp[mp[src]]+1);
            mp[src]=i;
            src=strAdd(strnum[i],j);
            if(mp.count(src)>0)
                dp[i]=max(dp[i],dp[mp[src]]+1);
            mp[src]=i;
        }
        string src=strAdd(strnum[i],strnum[i].size());
        if(mp.count(src)>0)
            dp[i]=max(dp[i],dp[mp[src]]+1);
        mp[src]=i;
        ans=max(ans,dp[i]+1);
    }
    cout<<ans<<endl;
    return 0;
}