link:http://www.bnuoj.com/bnuoj/problem_show.php?pid=26109

无语了~~~比赛做了差不多了,看到没什么做了,就扔在一边在那儿开始玩了、、、、

后来sjw问我d怎么样,我就看了一下,发现做的人也蛮多的了,就读了一下题。。。。

发现这是纯字符串编辑距离的模板题哇。。。。

正好以前收集过这个的模板,就套了一下,唉。。无语的时间来不及了。。。。

交的时候已经刚刚结束,手速嫌慢啊。。。接受这次教训!!!

下面是我的代码,可以当做编辑距离的模板,题意就是问字符串之间的编辑距离小于一个数的有多少。。

把模板改一下即可

code:

#include <stdio.h>
#include <string.h>
char mag[1501][100];
int dp[20][20];
char str[20];
int min(int a,int b,int c)
{
int min = a;
if(b < min)
min = b;
if(c < min)
min = c;
return min;
}

int main()
{
int t,cas,i,j,k,p,q,cnt;
int n,m,thr;
scanf(“%d”,&t);
for(cas=1;cas<=t;cas++)
{
printf(“Case #%d:\n”, cas);
scanf(“%d%d”,&n,&m);
for(i=0;i<n;i++)
{
scanf(“%s”,mag[i]);
}
for(i=0;i<m;i++)
{
scanf(“%s%d”,str,&thr);
cnt=0;
for(j=0;j<n;j++)
{
int len=strlen(mag[j]),len1=strlen(str);
for(k=0;k<=len1;k++)
dp[0][k]=k;
for(k=0;k<=len;k++)
dp[k][0]=k;
for(p=1;p<=len;p++)
for(q=1;q<=len1;q++)
if(mag[j][p-1]==str[q-1])
dp[p][q] = min(dp[p-1][q-1],dp[p-1][q] + 1,dp[p][q-1] + 1);
else dp[p][q] = min(dp[p-1][q-1] + 1,dp[p-1][q] + 1,dp[p][q-1] + 1);
if(dp[len][len1]<=thr)
cnt++;
}
printf(“%d\n”,cnt);
}

}
return 0;
}

 

发表评论

电子邮件地址不会被公开。

Post Navigation