HDU 4323 Magic Number（编辑距离DP）

http://acm.hdu.edu.cn/showproblem.php?pid=4323

题意：

给出n个串和m次询问，每个询问给出一个串和改变次数上限，在不超过这个上限的情况下，n个串中有多少个串可以转化为询问中给的串。

 

思路：

明显的编辑距离DP，直接暴力过了，网上有用bk树的，可惜我不会。

1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 6 int n, m; 7 char s[1505][1005]; 8 char tmp[1005]; 9 int dp[1005][1005]; 10 11 int main() 12 { 13 //freopen("in.txt","r",stdin); 14 int T; 15 int kase = 0; 16 scanf("%d",&T); 17 while(T--) 18 { 19 scanf("%d%d",&n,&m); 20 for(int i=1;i<=n;i++) scanf("%s",s[i]); 21 printf("Case #%d:\n",++kase); 22 while(m--) 23 { 24 int ans = 0; 25 int x; scanf("%s%d",tmp,&x); 26 for(int t=1;t<=n;t++) 27 { 28 int n1 = strlen(s[t]); 29 int n2 = strlen(tmp); 30 for(int i=0;i<=n1;i++) dp[i][0] = i; 31 for(int i=0;i<=n2;i++) dp[0][i] = i; 32 for(int i=1;i<=n1;i++) 33 for(int j=1;j<=n2;j++) 34 { 35 dp[i][j] = min(dp[i-1][j],dp[i][j-1])+1; 36 dp[i][j] = min(dp[i][j],dp[i-1][j-1]+(s[t][i-1]!=tmp[j-1])); 37 } 38 if(dp[n1][n2]<=x) ans++; 39 } 40 printf("%d\n",ans); 41 } 42 } 43 return 0; 44 }

 

转载于:https://www.cnblogs.com/zyb993963526/p/7898249.html

总结

以上是生活随笔为你收集整理的HDU 4323 Magic Number（编辑距离DP）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。