1 #include <stack>  2 #include <iostream>  3 #include <stdio.h>  4 #define R19 0  5 #define R20 1  6 #define R21 2  7 #define INF 1000000000  8 using namespace std;  9  10 char ch[28][22][22]; 11 char mat[1210][22]; 12 int dif[28][22][1210]; 13 int cost[1210][4]; // cost[i][j]表示从mat的第i行开始匹配j行得到的最小差距 14 int optimalCh[1210][4]; // optimalCh[i][j]表示从mat的第i行开始匹配j行最优的匹配字符 15 int d[1210]={0}; // d[i]表示匹配到第i行所得到的最小差距 16 int step[1210]; // step[i]表示第i行开始的最优匹配的字符行数 17 // 得到行数中不同的个数 18 /* 19 num为第几个字符 20 l1为num字符的行数 21 l2为mat的行数 22 */ 23 int getDif(int num,int l1,int l2) 24 { 25     int sum=0; 26     for(int i=0;i<20;i++) 27     { 28         if(ch[num][l1][i]!=mat[l2][i]) 29             sum++; 30     } 31     return sum; 32 } 33  34 // num为字符，l1为mat开始匹配的行数，del为删除了哪一行 35 int getCost(int num,int l1,int del) 36 { 37     int sum=0; 38     for(int i=0,p=0;p<19;i++,p++) 39     { 40         if(i==del) 41             i++; 42         sum+=dif[num][i][l1+p]; 43     } 44     return sum; 45 } 46  47 int getCost2(int num,int l1,int del) 48 { 49     int sum=0; 50     for(int i=0,p=0;i<20;i++,p++) 51     { 52         if(p==del) 53             p++; 54         sum+=dif[num][i][p+l1]; 55     } 56     return sum; 57 } 58  59  60 int main() 61 { 62     freopen("font.in","r",stdin); 63     int n; // 行数 64     cin>>n; 65     for(int i=0;i<n/20;i++) 66     { 67         for(int j=0;j<20;j++) 68         { 69             scanf("%s",ch[i][j]); 70  71         } 72     } 73  74     freopen("charrec.in","r",stdin); 75     freopen("charrec.out","w",stdout); 76  77     cin>>n; 78  79     for(int i=0;i<n;i++) 80         scanf("%s",mat[i]); 81  82     // 初始化dif数组 83     for(int i=0;i<27;i++) 84         for(int j=0;j<20;j++) 85         { 86             for(int k=0;k<n;k++) 87             { 88                 dif[i][j][k]=getDif(i,j,k); 89             } 90         } 91  92     // 初始化cost 93     for(int i=0;i<n;i++) // 从第i行开始匹配 94     { 95         cost[i][R19]=cost[i][R20]=cost[i][R21]=INF; 96         for(int j=0;j<27;j++) // 第j个字符 97         { 98             if(i+19<n+1) 99             {100                 for(int k=0;k<20;k++) // 删掉行数101                 {102                     if(cost[i][R19]>getCost(j,i,k))103                     {104                         cost[i][R19]=getCost(j,i,k);105                         optimalCh[i][R19]=j;106                     }107                 }108             }109             if(i+20<n+1)110             {111                 if(cost[i][R20]>getCost(j,i,-1))112                 {113                     cost[i][R20]=getCost(j,i,-1);114                     optimalCh[i][R20]=j;115                 }116             }117             if(i+21<n+1)118             {119                 for(int k=0;k<21;k++) // 多出的行数120                 {121                     if(cost[i][R21]>getCost2(j,i,k))122                     {123                         cost[i][R21]=getCost2(j,i,k);124                         optimalCh[i][R21]=j;125                     }126                 }127             }128         }129     }130 131     fill_n(d,n+5,INF);132     // 初始值133     d[18]=cost[0][R19];step[18]=19;134     d[19]=cost[0][R20];step[19]=20;135     d[20]=cost[0][R21];step[20]=21;136     // DP137     for(int i=21;i<n;i++) // 匹配的最后一行为i138     {139         if(d[i-19]+cost[i-18][R19]<d[i])140         {141             d[i]=d[i-19]+cost[i-18][R19];142             step[i]=19;143         }144         if(d[i-20]+cost[i-19][R20]<d[i])145         {146             d[i]=d[i-20]+cost[i-19][R20];147             step[i]=20;148         }149         if(d[i-21]+cost[i-20][R21]<d[i])150         {151             d[i]=d[i-21]+cost[i-20][R21];152             step[i]=21;153         }154     }155 156     stack<int> S;157 158     for(int p=n-1;p!=-1;p=p-step[p])159     {160         S.push(optimalCh[p-step[p]+1][step[p]-19]);161     }162 163     while(!S.empty())164     {165         int tmp=S.top();166         S.pop();167         printf("%c",tmp==0?‘ ‘:tmp-1+‘a‘);168     }169     cout<<endl;170     return 0;171 }