题目大意
一个字符可以表示成一个20*20的01矩阵。它们都在一个叫“fout.in”,共有27个字符，就是空格+小写字母（按字典序从小到大排序）。现在要翻译一个N*20的01矩阵，也就是按“fout.in”匹配每个字符，最后N*20的矩阵变成一个字符串。可惜的是这个N*20的矩阵可能遭到破坏。
每个字符可能遭到如下破坏
1、最多有一行可能被复制了（就接在原来那一行的下面）
2、最多有一行可能丢失了
3、有些“0”可能被改成“1”
4、有些“1”可能被改成“0”
被复制的一行也有可能被替换01。也就是1可以和3，4搭配来破坏每一个字符的矩阵（也就是20*20的矩阵），2可以和3，4搭配，但1和2不可以搭配，就是说不可能被复制一行有丢失一行。如果替换01的个数是大于每个字符的矩阵的30%的，则视为不能匹配。被复制的一行和原来的一行按和匹配01误差最小的一行计算。
求误差最小的匹配。
题解
这题的题目描述细节有点多。
不过只要细心就行了。
一种简单而神奇的DP。
其实有三种情况，19、20、21行的01矩阵。和文件里的20行的01矩阵匹配。我们都每种搞出每种最小的来。
DP很简单：f[第i行] = min{f[i - 19] + 第i-18行到第i行的丢失一行的最小匹配, f[i - 20] + 直接匹配, f[i - 21] + 多出一行}
/*TASK:charrecLANG:C++*/#include#include #include #include using namespace std;const char *str = " abcdefghijklmnopqrstuvwxyz";char sf[545][25], s[1205][25], rec[1205][3];int mini[1205][3], f[1205], nf, n, mat[1205][545];string ss[1205];void readfont(){ FILE *fl; fl = fopen("font.in", "r"); fscanf(fl, "%d", &nf); for (int i = 1; i <= nf; ++i) fscanf(fl, "%s", sf[i]); fclose(fl);}int match(int l1, int l2){ int cnt = 0; for (int i = 0; i < 20; ++i) if (s[l1][i] != sf[l2][i]) cnt++; return cnt;}int main(){ readfont(); freopen("charrec.in", "r", stdin); freopen("charrec.out", "w", stdout); scanf("%d", &n); for (int i = 1; i <= n; ++i) scanf("%s", s[i]); memset(mini, 0x7f, sizeof(mini)); for (int i = 1; i <= nf; ++i) for (int j = 1; j <= n; ++j) mat[j][i] = match(j, i); for (int k = 1; k <= nf; k += 20) { for (int i = 1; i <= n; ++i) { if (i + 19 <= n) { int tmp = 0; for (int l = 1; l <= 20; ++l) tmp += mat[i + l - 1][k + l - 1]; if (tmp < mini[i][1]) { rec[i][1] = (tmp > 120 ? '?' : str[k / 20]); mini[i][1] = tmp; } } for (int j = 1; j <= 21; ++j) { if (j < 21 && i + 18 <= n) { int tmp = 0; for (int l = 1; l < j; ++l) tmp += mat[i + l - 1][k + l - 1]; for (int l = j; l <= 19; ++l) tmp += mat[i + l - 1][k + l]; if (tmp < mini[i][0]) { rec[i][0] = (tmp > 120 ? '?' : str[k / 20]); mini[i][0] = tmp; } } if (i + 20 <= n) { int tmp = 0; for (int l = 1; l < j; ++l) tmp += mat[i + l - 1][k + l - 1]; for (int l = j; l <= 21; ++l) tmp += mat[i + l][k + l - 1]; if (tmp < mini[i][2]) { rec[i][2] = (tmp > 120 ? '?' : str[k / 20]); mini[i][2] = tmp; } } } } } f[0] = 0; ss[0] = ""; for (int i = 1; i < 19; ++i) ss[i] = "?", f[i] = 121; for (int i = 19; i <= n; ++i) { f[i] = f[i - 19] + mini[i - 18][0]; ss[i] = ss[i - 19] + rec[i - 18][0]; if (i > 19 && f[i] > f[i - 20] + mini[i - 19][1]) { f[i] = f[i - 20] + mini[i - 19][1]; ss[i] = ss[i - 20] + rec[i - 19][1]; } if (i > 20 && f[i] > f[i - 21] + mini[i - 20][2]) { f[i] = f[i - 21] + mini[i - 20][2]; ss[i] = ss[i - 21] + rec[i - 20][2]; } } cout << ss[n] << endl; return 0;}