UVA 10029 Edit Step Ladders ——（DAG求最长路）

　　题意：升序的给出一本若干个单词，每个单词都可删除一个字母，添加一个字母或者改变一个字母，如果任意一个操作以后能变成另外一个字典中的单词，那么就连一条有向边，求最长的长度。

　　分析：DAG的最长路和最短路在算法竞赛入门里边原原本本有的，结果我现在忘记了，，真是太弱了。。方法就是，用map对应键值（以建图），然后删除操作和修改操作可以看做同一个操作，之后每个操作都是在相应的位置添加一个 '*' 就可以了。想说的有两点，一个是为什么删除和修改可以看做一个操作，其实删除这个操作根本就是多余的，因为一个单词比方说add要和ad匹配，不一定要add删除，而是可以ad添加一个d，所以说删除操作是多余的；第二点是添加操作时，要注意两头都是可以放 '*' 的。

　　建完图以后用求DAG的最长路的方法进行dp即可。

　　具体见代码：

#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <string>
#include <map>
#include <vector>
#include <iostream>
using namespace std;
const int N = 25000+5;

string s[N];
vector<int> G[N];
map<string,int> M;
int dp[N];

string change(string s,int pos) //删除操作和改变操作可以看做是一样的
{
    string ans = "";
    for(int i=0;i<s.size();i++)
    {
        if(pos == i) ans += '*';
        else ans += s[i];
    }
    return ans;
}

string add(string s,int pos)
{
    string ans = "";
    for(int i=0;i<s.size();i++)
    {
        if(pos == i) ans += '*';
        ans += s[i];
    }
    if(pos == s.size()) ans += '*';
    return ans;
}

int dfs(int x)   //dfs求DAG的最长边
{
    if(dp[x] != -1) return dp[x];
    int ans = 0;
    for(int i=0;i<G[x].size();i++)
    {
        int v = G[x][i];
        ans = max(ans,dfs(v));
    }
    return dp[x] = ans + 1;
}

int main()
{
    int cnt = 0;
    while(cin>>s[cnt++]);

    for(int i=0;i<cnt;i++)
    {
        for(int j=0;j<s[i].size();j++)
        {
            string t = change(s[i],j);
            if(M.count(t))
            {
                G[M[t]].push_back(i);
            }
            M[t] = i;
        }

        for(int j=0;j<=s[i].size();j++)
        {
            string t = add(s[i],j);
            if(M.count(t))
            {
                G[M[t]].push_back(i);
            }
            M[t]=i;
        }
    }

    memset(dp,-1,sizeof(dp));
    int ans = 0;
    for(int i=0;i<cnt;i++)
    {
        ans = max(ans,dfs(i));
    }

    printf("%d
",ans);
    return 0;
}