hdu 4323 Magic Number dp 多校联合赛（三）第四题

如果a[i],b[j]相等dp[i][j]=dp[i-1][j-1]; 如果不想等 dp[i][j]=min(dp[i-1][j],min(dp[i][j-1],dp[i-1][j-1]))+1;

注意最后dp[lena-1][lenb-1]<=y就行，

#include<iostream>#include<cstdio>#include<string.h>using namespace std;int n,m,dp[15][15];int y;int judge(char a[],char b[]){    int lena=strlen(a);    int lenb=strlen(b);    if(lena-lenb>y||lenb-lena>y)        return 10;//    cout<<lena<<" "<<lenb<<endl;    for(int i=0;i<lena;i++)        dp[i][0]=i;    for(int i=0;i<lenb;i++)        dp[0][i]=i;    for(int i=1;i<lena;i++){        for(int j=1;j<lenb;j++){            if(a[i]==b[j]) dp[i][j]=dp[i-1][j-1];            else dp[i][j]=min(dp[i-1][j],min(dp[i][j-1],dp[i-1][j-1]))+1;        }    }    return dp[lena-1][lenb-1];}char a[1605][15],b[15];int main(){    int t,p=1;    scanf("%d",&t);    while(t--){        scanf("%d%d",&n,&m);        for(int i=0;i<n;i++){            a[i][0]='*';            scanf("%s",a[i]+1);        }        printf("Case #%d:\n",p++);        while(m--){            scanf("%s%d",b+1,&y);            b[0]='*';            int sum=0;            for(int i=0;i<n;i++){                if(judge(a[i],b)<=y)                sum+=1;            }            printf("%d\n",sum);        }    }    return 0;}