uva 10029 - Edit Step Ladders(dp + 二分）

题目链接：10029 - Edit Step Ladders

题目大意：给出若干个按照字典序排列的字符串，每两个字符串之间可以存在一个梯度，也可不存在，所谓梯度就是指前一个字符串同过改变、删除或填加一个字符，是转化后的字符串等于后面一个字符串，问，在所给出的若干个字符串中最多能连续通过梯度连接多少个字符串，输出最大值。

解题思路：类似与LIS，可是用o(n^2)的算法却超时，然后上网查题解一直不能理会如何用二分的方法在前面的字符串中找匹配，后来才知道给出的字符串是按照字典序排列的，这样的话等于是一个有序的序列，完全可以将当前前字符串的所有变换字符串去用二分搜索出来。

#include <stdio.h>#include <string.h>#define max(a, b) (a) > (b) ? (a) :(b)const int N = 25005;const int M = 20;int n = 0, dp[N], ans = 1;char word[N][M];void add(char *a, char *s, char ch, int in) {int i;for (i = 0; i < in; i++)s[i] = a[i];s[in] = ch;for ( ; a[i]; i++)s[i + 1] = a[i];s[i + 1] = '\0';}void del (char *a, char *s, int in) {int i;for (i = 0; i < in; i++)s[i] = a[i];for (i++; a[i]; i++)s[i - 1] = a[i];s[i - 1] = '\0';}void change(char *a, char *s, char ch, int in) {int i;for (i = 0; a[i]; i++)s[i] = a[i];    s[in] = ch;s[i] = '\0';}void handle(char *now, char *s, char ch, int t, int flag) {if (flag == 0) change(now, s, ch, t);else if (flag == 1) del(now, s, t);else add(now, s, ch, t);}int search(char *s, int r) {r--;int l = 0, mid;while (l <= r) {mid = (l + r) / 2;int flag = strcmp(word[mid], s);if (flag == 0) return mid;else if (flag < 0) l = mid + 1;else r = mid - 1;}return -1;}int main() {char str[M];while (scanf("%s", word[n]) == 1) n++;for (int i = 0; i < n; i++) {dp[i] = 1;for (int k = 0; k < 3; k++) {for (int j = 0; word[i][j]; j++) {for (int t = 0; t < 26; t++) {handle(word[i], str, 'a' + t, j, k);if (strcmp(word[i], str) < 0) break;int f = search(str, i);if (f >= 0)dp[i] = max(dp[i], dp[f] + 1);}}}ans = max(ans, dp[i]);}printf("%d\n", ans);return 0;}