题意：给你n个数，m个查询，查询中包括一个数和一个最大编辑距离d，问n个数中和这个数的编辑距离不超过d的有多少个
编辑距离：http://baike.baidu.com/view/2020247.htm?from_id=792226&type=syn&fromtitle=Levenshtein+Distance&fr=aladdin
思路：设dp[i][j]为数字a前i个数和数字b前j个数的编辑距离
则dp[i][j]=min（dp[i-1][j]+1,dp[i][j-1+1,dp[i-1][j-1]+cost)
交一发，T了，这里有个小小的优化，若两个数的长度之差大于最大编辑距离d，则不必再求他们之间的编辑距离
代码
#include "stdio.h"
#include "string.h"
#include "stdlib.h"
#include "math.h"
#define INF 1000
char a[][],b[];
int dp[][];
int min(int a,int b)
{
return a<b?a:b;
}
void debug(int len1,int len2)
{
int i,j;
for(i=;i<=len1;i++)
{for(j=;j<=len2;j++)
printf("%d ",dp[i][j]);
printf("\n");
}
}
int slove(char a[],char b[])
{
int len1,len2;
int i,j;
int cost;
len1=strlen(a);
len2=strlen(b);
memset(dp,,sizeof(dp));
for(i=;i<len1;i++)
dp[i+][]=i+;
for(i=;i<len2;i++)
dp[][i+]=i+;
for(i=;i<len1;i++)
{
for(j=;j<len2;j++)
{
if(a[i]==b[j])
cost=;
else
cost=;
dp[i+][j+]=min(dp[i][j+]+,dp[i+][j]+);
dp[i+][j+]=min(dp[i][j]+cost,dp[i+][j+]);
}
}
//printf("%s %s:\n",a,b);
//debug(len1,len2);
return dp[len1][len2];
}
int main()
{
int n,m;
int t;
int i,j;
int d,cas=;
int ans;
int len1,len2;
scanf("%d",&t);
while(t--)
{
cas++;
printf("Case #%d:\n",cas);
scanf("%d%d",&n,&m);
for(i=;i<n;i++)
scanf("%s",a[i]);
while(m--)
{
ans=;
scanf("%s%d",b,&d);
for(j=;j<n;j++)
{
len1=strlen(a[j]);
len2=strlen(b);
if(abs(len1-len2)>d)
continue;
if(slove(a[j],b)<=d)
ans++;
}
printf("%d\n",ans);
}
}
return ;
}