題目：已知一些字典序排列的單詞，問能從中找到最大的一個有序單詞集合，
使得集合中的單詞每一個是有上一個單詞經過一次變換得來的（增、刪、改）。
分析：dp，LIS。最大遞增子序列，不過數據較大须要優化。
因為，不是每一個單詞都是还有一個單詞的前驅，所以非常多查找是不必要的。
所以，利用每個單詞進行變換求出全部前驅，然後查找前驅是否在前面出現過；
假设出現過。則能够更新LIS。查找前驅的過程使用二分優化就可以節約時間。
說明：本來先用hash表+記憶化搜索，效率較低╮(╯▽╰)╭。
#include <cstring>
#include <cstdio>#define max(a, b) ((a)>(b)?(a):(b))char list[25005][17], now[17], New[17];
int dp[25005];int binary_search(int r, char words[])
{
int l = 0, mid = 0, cmp;
while (l <= r) {
mid = (l+r)>>1;
cmp = strcmp(list[mid], words);
if (!cmp) return mid;
if (cmp > 0) r = mid-1;
else l = mid+1;
}
return -1;
}int main()
{
int size = 0;
while (~scanf("%s",list[size])) ++ size;int maxv = 0;
for (int p = 0; p < size; ++ p) {
dp[p] = 1;
strcpy(now, list[p]);
int length = strlen(now), point = -1;
//删除元素
for (int i = 0; i < length; ++ i) {
if (now[i] < now[i+1]) continue;
int count = 0;
for (int j = 0; j < length; ++ j)
if (i != j) New[count ++] = now[j];
New[count ++] = 0;
point = binary_search(p-1, New);
if (point >= 0 && dp[p] <= dp[point])
dp[p] = dp[point]+1;}
//加入元素
for (int i = 0; i <= length; ++ i)
for (char k = 'a'; k <= 'z'; ++ k) {
if (k > now[i]) continue;
int count = 0;
for (int j = 0; j <= length; ++ j) {
if (i == j) New[count ++] = k;
New[count ++] = now[j];
}
New[count ++] = 0;
point = binary_search(p-1, New);
if (point >= 0 && dp[p] <= dp[point])
dp[p] = dp[point]+1;
}
//改变元素
for (int i = 0; i < length; ++ i)
for (char k = 'a'; k < now[i]; ++ k) {
strcpy(New, now);
New[i] = k;
point = binary_search(p-1, New);
if (point >= 0 && dp[p] <= dp[point])
dp[p] = dp[point]+1;
}
maxv = max(maxv, dp[p]);
}printf("%d\n",maxv);
return 0;
}
