HDU 4271 Find Black Hand [最短编辑距离DP]

　　这么水的一道最短编辑距离DP，比赛的时候居然没有去做。。

　　很裸的最短编辑距离DP，就是要注意环的问题。因为如果直接copy两遍的话，有可能会将本来是同一个位置的字母使用两次。但是可以发现串的长度只有10，最大的编辑距离不会超过10，当原串长度>2*L时环就没有影响了，因为这时如果环中一个字母被使用两次，那最短编辑距离肯定已经大于L了。

　　我是长度小于20时暴力枚举，大于30时在原串后面copy原创的前20个字符。

#include <stdio.h>
#include <string.h>
#include <algorithm>
#define INF 0x3fffffff
#define MAXN 100105
int n,l1,l2,ans,tmp;
char s1[MAXN],s2[12][12],ansid;
int d[12][MAXN];
inline int min(const int &x,const int &y){return x<y?x:y;}
int dp(char *s1,char *s2,int l1,int l2){
    int ret=INF;
    for(int i=1;i<=l1;i++){
        d[i][0]=i;
        for(int j=1;j<=l2;j++){
            d[i][j]=min(d[i-1][j-1]+(s1[i-1]!=s2[j-1]),min(d[i-1][j],d[i][j-1])+1);
            if(i==l1)ret=min(ret,d[i][j]);
        }
    }
    return ret;
}
int main(){
    //freopen("test.in","r",stdin);
    while(scanf("%s",s1)!=EOF){
        l1=strlen(s1);
        scanf("%d",&n);
        ans=INF,ansid=-1;
        for(int i=0;i<n;i++){
            scanf("%s",s2[i]);
            l2=strlen(s2[i]);
            tmp=INF;
            if(l1<20){
                for(int j=0;j<l1;j++){
                    tmp=std::min(tmp,dp(s2[i],s1+j,l2,l1));
                    s1[l1+j]=s1[j];
                }
            }else{
                for(int j=0;j<20;j++)s1[l1++]=s1[j];
                tmp=dp(s2[i],s1,l2,l1);
            }
            if(tmp<ans||tmp==ans&&strcmp(s2[i],s2[ansid])<0){
                ansid=i,ans=tmp;
            }
        }
        printf("%s %d\n",s2[ansid],ans);
    }
    return 0;
}