题目大意
一个字符可以表示成一个2020的01矩阵。它们都在一个叫“fout.in”,共有27个字符,就是空格+小写字母(按字典序从小到大排序)。现在要翻译一个N20的01矩阵,也就是按“fout.in”匹配每个字符,最后N20的矩阵变成一个字符串。可惜的是这个N20的矩阵可能遭到破坏。
每个字符可能遭到如下破坏
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:charrec
LANG:C++
*/
#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
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;
}
原文链接: https://www.cnblogs.com/albert7xie/p/5224303.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/229315
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!