USACO Character Recognition

题目要求输出最接近输入数据的字符串，我们可以使用动态规划达到这个目的：
用opt[i]表示前i行最小的改变量，那么容易得出状态转移方程（叙述起来比较麻烦，请看代码114行～148行）。
由于题目要输出字符序列，因此使用prev,store分别记录前一个字符的开始位置和对应的字符。
不过，我第一次提交的程序在第8个测试点超时了。检查发现，每一次比较每两行字符的区别时，我使用的都是最朴素的方法，因为动态规划过程中要多次用到这些数据，这样以来就耗费了很多时间。于是，加上了linediff数组，用于储存font.in和charrec.in每行之间的差异，并预先计算（见36行init函数），需要时直接取出。

C语言: 高亮代码由发芽网提供

001 #include <stdio.h>
002 #include <stdlib.h>
003 #include <string.h>
004 #define MAXLINE 1220
005 #define FONTN 27
006 #define INF 100000000
007
008 char corr[] = " abcdefghijklmnopqrstuvwxyz";
009 char font[FONTN][20][21];
010 int N;
011 char str[MAXLINE][21];
012 int opt[MAXLINE];
013 int prev[MAXLINE];
014 char store[MAXLINE];
015 int linediff[MAXLINE][FONTN][20];   //[line][fontnumber][fontline]  precalculate
016
017 void readfont()
018 {
019     int i,j;
020     freopen("font.in","r",stdin);
021     scanf("%d\n",&i);
022     for(i = 0;i < 27;i ++)
023         for(j = 0;j < 20;j ++)
024             scanf("%s\n",font[i][j]);
025 }
026
027 void readinput()
028 {
029     freopen("charrec.in","r",stdin);
030     scanf("%d\n",&N);
031     int i;
032     for(i = 0;i < N;i ++)
033         scanf("%s\n",str[i]);
034 }
035
036 void init()    //calculate linediff array
037 {
038     int i,j,k,t;
039     for(i = 0;i < N;i ++)
040         for(j = 0;j < FONTN;j ++)
041             for(k = 0;k < 20;k ++)
042             {
043                 linediff[i][j][k] = 0;
044                 for(t = 0;t < 20;t ++)
045                     if(font[j][k][t] != str[i][t])    linediff[i][j][k] ++;
046             }
047 }
048
049 int get_min(int a,int b)
050 {
051     if(a < b)    return a;
052     return b;
053 }
054
055 int cmp_normal(int l,int f)
056 {
057     int d;
058     int i;
059     for(i = d = 0;i < 20;i ++)
060         d += linediff[l ++][f][i];
061     return d;
062 }
063
064 int cmp_missing(int l,int f)
065 {
066     int d,tmp;
067     int missline,i,j;
068     d = INF;
069     for(missline = 0;missline < 20;missline ++)
070     {
071         tmp = 0;j = l;
072         for(i = 0;i < 20;i ++)
073         {
074             if(missline == i)    continue;
075             tmp += linediff[j ++][f][i];
076         }
077         d = get_min(d,tmp);
078     }
079     return d;
080 }
081
082 int cmp_dup(int l,int f)
083 {
084     int d,tmp;
085     int dupline,i,j;
086     d = INF;
087     for(dupline = 0;dupline < 20;dupline ++)
088     {
089         tmp = 0;j = l;
090         for(i = 0;i < 20;i ++)
091         {
092             if(i == dupline)
093             {
094                 tmp += get_min(linediff[j][f][i],linediff[j + 1][f][i]);
095                 j += 2;
096                 continue;
097             }
098             tmp += linediff[j ++][f][i];
099         }
100         d = get_min(d,tmp);
101     }
102     return d;
103 }
104
105 void dp()
106 {
107     int i,j;
108     //i:line
109     //j:alpha for test
110     int tmp;
111     opt[0] = 0;
112     for(i = 1;i < MAXLINE;i ++)
113         opt[i] = INF;
114     for(i = 0;i < N;i ++)
115     {
116         if(opt[i] == INF)    continue;
117         if(i + 19 <= N)
118             for(j = 0;j < 27;j ++)
119             {
120                 tmp = opt[i] + cmp_missing(i,j);
121                 if(tmp < opt[i + 19])
122                 {
123                     store[i + 19] = corr[j];
124                     opt[i + 19] = tmp;
125                     prev[i + 19] = i;
126                 }
127             }
128         if(i + 20 <= N)
129             for(j = 0;j < 27;j ++)
130             {
131                 tmp = opt[i] + cmp_normal(i,j);
132                 if(tmp < opt[i + 20])
133                 {
134                     store[i + 20] = corr[j];
135                     opt[i + 20] = tmp;
136                     prev[i + 20] = i;
137                 }
138             }
139         if(i + 21 <= N)
140             for(j = 0;j < 27;j ++)
141             {
142                 tmp = opt[i] + cmp_dup(i,j);
143                 if(tmp < opt[i + 21])
144                 {
145                     store[i + 21] = corr[j];
146                     opt[i + 21] = tmp;
147                     prev[i + 21] = i;
148                 }
149             }
150     }
151 }
152
153 void pt()
154 {
155     int i;
156     int top = 0;
157     char ans[100];
158     for(i = N;i > 0;i = prev[i])
159         ans[top ++] = store[i];
160     while(top --)
161         printf("%c",ans[top]);
162     printf("\n");
163 }
164
165 int main()
166 {
167     freopen("charrec.out","w",stdout);
168     readfont();
169     readinput();
170     init();
171     dp();
172     pt();
173     fclose(stdout);
174     fclose(stdin);
175     return 0;
176 }