记录编号	404659	评测结果	AAAAAAAAA
题目名称	[IOI 1997][USACO]字符识别	最终得分	100
用户昵称	Imone NOI2018Au	是否通过	通过
代码语言	C++	运行时间	2.298 s
提交时间	2017-05-14 09:52:38	内存使用	0.36 MiB

#include <cstring>
#include <cstdio>
#define INF 0x3f3f3f3f
inline char int2chr(int x) {
	return !x ? ' ' : 'a' + (x - 1);
}

char G[30][30][30];

int cmp20(char str[][30], char &res) {
	int i, k, p, minv = INF, minc, curv;
	for(i=0;i<27;i++) {
		curv = 0;
		for(k=0;k<20;k++) {
			for(p=0;p<20;p++) curv += str[k][p] != G[i][k][p];
		}
		if(curv < minv) {
			minv = curv; minc = i;
		}
	}
	res = int2chr(minc);
	return minv;
}

int cmp21(char str[][30], char &res) {
	int id, i, k, p, minv = INF, minc, curv, curlno;
	for(id=1;id<21;id++) {
		for(i=0;i<27;i++) {
			curv = 0; curlno = 0;
			for(k=0;k<21;k++) if(k != id) {
				for(p=0;p<20;p++) curv += G[i][curlno][p] != str[k][p];
				curlno++;
			}
			if(curv < minv) {
				minv = curv; minc = i;
			}
		}
	}
	res = int2chr(minc);
	return minv;
}

int cmp19(char str[][30], char &res) {
	int id, i, k, p, minv = INF, minc, curv, curlno;
	for(i=0;i<27;i++) {
		for(id=0;id<20;id++) {
			curv = 0; curlno = 0;
			for(k=0;k<20;k++) if(k != id) {
				for(p=0;p<20;p++) curv += G[i][k][p] != str[curlno][p];
				curlno++;
			}
			if(curv < minv) {
				minv = curv; minc = i;
			}
		}
	}
	res = int2chr(minc);
	return minv;
}

char M[1210][30];

int dp[1210];
int dp_par[1210];
char dp_chr[1210];
char dp_res[100];

int N, Nres = 0;

int main() {
	freopen("charrec1.in", "rt", stdin);
	freopen("charrec1.out", "wt", stdout);
	
	int i, k; scanf("%d", &N);
	for(i=0;i<27;i++) {
		for(k=0;k<20;k++) scanf("%s", G[i][k]);
	}

	scanf("%d", &N);
	for(i=1;i<=N;i++) scanf("%s", M[i]);
	
	memset(dp, 0x3f, sizeof(dp)); dp[0] = 0;
	for(i=19;i<=N;i++) {
		int minv = INF, curv, minfrom; char minchar, curchar;
		if(dp[i-19] < INF && (curv = dp[i-19] + cmp19(&M[i-19+1], curchar)) < minv) {
			minv = curv; minchar = curchar; minfrom = i-19;
		}
		if(i >= 20 && dp[i-20] < INF && (curv = dp[i-20] + cmp20(&M[i-20+1], curchar)) < minv) {
			minv = curv; minchar = curchar; minfrom = i-20;
		}
		if(i >= 21 && dp[i-21] < INF && (curv = dp[i-21] + cmp21(&M[i-21+1], curchar)) < minv) {
			minv = curv; minchar = curchar; minfrom = i-21;
		}
		dp[i] = minv; dp_par[i] = minfrom; dp_chr[i] = minchar;
	}
	
	i = N;
	while(i) {
		dp_res[Nres++] = dp_chr[i];
		i = dp_par[i];
	}
	for(i=Nres-1;i>=0;i--) putchar(dp_res[i]);
}