本文主要是介绍uva 10029 HASH + DP，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
给一个字典，里面有好多单词。单词可以由增加、删除、变换，变成另一个单词，问能变换的最长单词长度。
解析：
HASH+dp
代码：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <stack>
#include <vector>
#include <queue>
#include <map>
#include <climits>
#include <cassert>
#define LL long longusing namespace std;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
const double pi = 4 * atan(1.0);
const double ee = exp(1.0);const int maxn = 25000 + 10;
const int HASH = 1000003;int n;
int head[HASH], next[maxn];
char s[maxn][20], t[20];
int dp[maxn];//hash ...
int Hash(char str[])
{int v = 0, seed = 88;while (*str)v = v * seed + *(str++);return (v & 0x7fffffff) % HASH;
}void Insert(int x)
{int h = Hash(s[x]);next[x] = head[h];head[h] = x;
}int Search()
{int i;int h = Hash(t);//for (i = head[h]; i != -1; i = next[i]){if (strcmp(t, s[i]) == 0){break;}}return i;
}//dp ...
void add(char str[], int pos, int key)
{memset(t, 0, sizeof(t));int i, j;for (i = 0, j = 0; i < pos; i++, j++){t[j] = str[i];}t[j++] = 'a' + key;for (; str[i]; i++, j++){t[j] = str[i];}t[j] = '\0';
}void del(char str[], int pos)
{memset(t, 0, sizeof(t));int i, j;for (i = 0, j = 0; i < pos; i++, j++){t[j] = str[i];}i++;for (; str[i]; i++, j++){t[j] = str[i];}t[j] = '\0';
}void change(char str[], int pos, int key)
{memset(t, 0, sizeof(t));strcpy(t, str);t[pos] = 'a' + key;
}int Dfs(int cur)
{if (dp[cur] != -1)return dp[cur];int res = 0;int len = strlen(s[cur]);//addfor (int i = 0; i <= len; i++){for (int k = 0; k < 26; k++){add(s[cur], i, k);int pos = Search();if (pos != -1 && strcmp(s[cur], t) < 0){int t = Dfs(pos) + 1;///posif (res < t){res = t;}}}}//deletefor (int i = 0; i < len; i++){del(s[cur], i);int pos = Search();if (pos != -1 && strcmp(s[cur], t) < 0){int t = Dfs(pos) + 1;///posif (res < t){res = t;}}}//changefor (int i = 0; i < len; i++){for (int k = 0; k < 26; k++){change(s[cur], i, k);int pos = Search();if (pos != -1 && strcmp(s[cur], t) < 0){int t = Dfs(pos) + 1;///posif (res < t){res = t;}}}}return dp[cur] = res;
}int main()
{
#ifdef LOCALfreopen("in.txt", "r", stdin);
#endif // LOCALn = 0;memset(head, -1, sizeof(head));while (scanf("%s", s[n]) != EOF){Insert(n);n++;}memset(dp, -1, sizeof(dp));int ans = 0;for (int i = 0; i < n; i++){int t = Dfs(i) + 1;if (ans < t){ans = t;}}printf("%d\n", ans);return 0;
}这篇关于uva 10029 HASH + DP的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
