UVA 10029 Edit Step Ladders（dp）

UVA 10029 Edit Step Ladders（dp）2014-04-10 csdn accelerator_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 w1, w2, ... wn such that the transformation from wi to wi+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

catdigdogfigfinfinefoglogwine

Sample Output

题意：给定一个字典，如果经过删除，添加或替换能转换成另一个单词，则这两个单词为阶梯变化，求出最长阶梯变化的字典。

思路：dp。lis，用n^2 超时了。。。然后没想明白看题解，发现有n（logn）方法。

把每个单词可以变换的情况全部弄出来，然后在前面进行2分查找，由于序列本身是字典序所以可行。这样就能过了

代码：

#include <stdio.h>#include <string.h>int max（int a, int b） {return a > b ？ a : b;}int min（int a, int b） {return a < b ？ a : b;}const int N = 25555, M = 20;char word[N][M], str[M];int n, i, j, k, l, dp[25555], ans;void change（char *word, char *str, char c, int wei） {int i;for （i = 0; word[i]; i ++）str[i] = word[i];str[wei] = c;str[i] = "";}void del（char *word, char *str, int wei） {int i;for （i = 0; i < wei; i ++）str[i] = word[i];for （i = wei + 1; word[i]; i ++）str[i - 1] = word[i];str[i - 1] = "";}void add（char *word, char *str, char c, int wei） {int i;for （i = 0; i < wei; i ++）str[i] = word[i];str[wei] = c;for （i = wei; word[i]; i ++）str[i + 1] = word[i];str[i + 1] = "";}void tra（char *word, char *str, char c, int wei, int flag） {if （flag == 0） change（word, str, c, wei）;else if （flag == 1） del（word, str, wei）;else add（word, str, c, wei）;}int find（char *str, int j） {int i = 0;j --;while （i <= j） {int mid = （i + j） / 2;if （strcmp（word[mid], str） == 0） {return mid;}else if （strcmp（word[mid], str） < 0） {i = mid + 1;}elsej = mid - 1;}return -1;}int main（） {while （gets（word[n]）） {n ++;}ans = 0;for （i = 0; i < n; i ++） {dp[i] = 1;for （k = 0; k < 3; k ++） {for （j = 0; word[i][j]; j ++） {for （l = 0; l < 26; l ++） {tra（word[i], str, "a" + l, j, k）;if （strcmp（word[i], str） < 0） break;int mid = find（str, i）;if （mid >= 0） dp[i] = max（dp[i], dp[mid] + 1）;}}}ans = max（ans, dp[i]）;}printf（"%d
", ans）;return 0;}