uva 10029 - Edit Step Ladders(巧妙构图 + Dag最长路)

最新推荐文章于 2025-05-04 14:28:46 发布

Wiking__acm

最新推荐文章于 2025-05-04 14:28:46 发布

阅读量2.1k

点赞数

分类专栏：动态规划

本文链接：https://blog.csdn.net/Wiking__acm/article/details/24382243

版权

动态规划专栏收录该内容

57 篇文章

订阅专栏

该博客介绍如何解决计算机科学竞赛问题UVA 10029，涉及编辑步梯的最长路径计算。通过对输入和输出格式的解释，以及示例的展示，作者引导读者理解并解决这个算法问题。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

Problem C: Edit Step Ladders

An edit step is a transformation from one word x to another word y such that x and y are words in the dictionary, and x can be transformed to y by adding, deleting, or changing one letter. So the transformation from dig to dog or from dog to do are both edit steps. An edit step ladder is a lexicographically ordered sequence of words w₁, w₂, ... w_n such that the transformation from w_i to w_i+1 is an edit step for all i from 1 to n-1 .

For a given dictionary, you are to compute the length of the longest edit step ladder.

Input

The input to your program consists of the dictionary - a set of lower case words in lexicographic order - one per line. No word exceeds 16 letters and there are no more than 25000 words in the dictionary.

Output

The output consists of a single integer, the number of words in the longest edit step ladder.

Sample Input

cat
dig
dog
fig
fin
fine
fog
log
wine

Sample Output

很容易想到最长路的建模。关键是，如果用n^2的方法一一比较每两个单词是否能达到去建边，肯定是会超时的。一种巧妙的方法是，考虑每个词所有可能的变化：删除和修改可以看成是一类的。这样，枚举出所有可能生成的词，注意，这里不要枚举所有可能的词的具体情况，这样就要考虑27种变化，事实上，可以用一个通配符比如‘*’代表这个字母可以是任意值。可以证明如果两个生成词相同，则它们一定可以在一步修改内到达。

建好图后再求一个最长路就可以了。

#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <iostream>
#include <stack>
#include <set>
#include <cstring>
#include <stdlib.h>
#include <cmath>
using namespace std;
typedef long long LL;
typedef pair<int, int> P;
const int maxn = 25000 + 5;

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

string change(string text, int pos){
    string ret = "";
    for(int i = 0;i < text.length();i++){
        if(i != pos) ret.push_back(text[i]);
        else ret.push_back('*');
    }
    return ret;
}

string add(string text, int pos){
    string ret = "";
    for(int i = 0;i < text.length();i++){
        if(pos == i) ret.push_back('*');
        ret.push_back(text[i]);
    }
    if(pos == text.length())
        ret.push_back('*');
    return ret;
}

int dp[maxn];

int dfs(int x){
    if(dp[x] != -1) return dp[x];
    int Max = 0;
    for(int i = 0;i < G[x].size();i++){
        int from = G[x][i];
        Max = max(Max, dfs(from));
    }
    return dp[x] = 1+Max;
}

int main(){
    int cnt = 0;
    while(cin >> s[cnt++]);
    cnt--;
    M.clear();
    for(int i = 0;i < cnt;i++) G[i].clear();
    for(int i = cnt-1;i >= 0;i--){
        for(int j = 0;j < s[i].length();j++){
            string tem = change(s[i], j);
            if(M.count(tem) > 0){
                G[M[tem]].push_back(i);
            }
            M[tem] = i;
        }
        for(int j = 0;j <= s[i].length();j++){
            string tem = add(s[i], j);
            if(M.count(tem) > 0){
                G[M[tem]].push_back(i);
            }
            M[tem] = i;
        }
    }

    memset(dp, -1, sizeof(dp));
    int ans = 0;
    for(int i = cnt-1;i >= 0;i--){
        ans = max(ans, dfs(i));
    }
    printf("%d\n", ans);

    return 0;
}