记录编号	185489	评测结果	AAAAAAAAA
题目名称	[IOI 1997][USACO]字符识别	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	3.870 s
提交时间	2015-09-07 10:38:39	内存使用	0.39 MiB

#include<cstdio>
#include<string>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int INF=0x7fffffff/2;
int N;
bool txt[1210][30];
bool visit[1210]={0};
//以txt被匹配第i行为状态，f记录最小变化量，F记录最小变化量下的字符串
string F[1210];
int f[1210]={0};
class miku
{
public:
	string s;
	bool map[30][30];
	void print()
	{
		cout<<s<<endl;
		for(int i=1;i<=20;i++)
		{
			for(int j=1;j<=20;j++)
				cout<<map[i][j];
			cout<<endl;
		}
	}
}P[30];
void readmap(int x)
{
	char a[30];
	for(int i=1;i<=20;i++)
	{
		scanf("%s",a);
		for(int j=1;j<=20;j++)
			P[x].map[i][j]=a[j-1]-'0';
	}
}
void read()
{
	int N1;
	scanf("%d",&N1);
	for(int i=0;i<=26;i++)
	{
		if(i==0)
			P[i].s=' ';
		else P[i].s='a'-1+i;
		readmap(i);
		//P[i].print();
	}
	scanf("%d",&N);
	char a[30];
	for(int i=1;i<=N;i++)
	{
		scanf("%s",a);
		for(int j=1;j<=20;j++)
			txt[i][j]=a[j-1]-'0';
	}
	//cout<<N<<endl;
}
int mate19(int B,int E,int &tem)
{
	int re=INF;
	for(int i=0;i<=26;i++)
	{
		for(int j=1;j<=20;j++)//枚举第几级行是缺少的
		{
			int temp=0;
			for(int k=1,k2=0;k<=20;k++,k2++)
			{
				if(k==j) k++;
				if(k>20) break;
				for(int t=1;t<=20;t++)
				{
					if(P[i].map[k][t]!=txt[B+k2][t]) temp++;
				}
			}
			if(temp<re)
			{
				re=temp;
				tem=i;
			}
		}
	}
	return re;
}
int mate20(int B,int E,int &tem)
{
	int re=INF;
	for(int i=0;i<=26;i++)
	{
		int temp=0;
		for(int j=1;j<=20;j++)
			for(int k=1;k<=20;k++)
			{
				if(P[i].map[j][k]!=txt[j+B-1][k]) temp++;
			}
		if(temp<re)
		{
			re=temp;
			tem=i;
		}
	}
    return re;	
}
int mate21(int B,int E,int &tem)
{
	int re=INF;
	for(int i=0;i<=26;i++)
	{
		for(int j=1;j<=20;j++)//枚举那一行是复制的
		{
			int temp=0;
			for(int k=1,k2=0;k<=20;k++,k2++)
			{
				if(k2==j) k2++;
				if(k2>20) break;
				for(int t=1;t<=20;t++)
				{
					if(P[i].map[k][t]!=txt[B+k2][t]) temp++;
				}
			}
			if(temp<re)
		    {
			    re=temp;
				tem=i;
		    }
		}
	}
	return re;
}
int DP(int x)
{
	if(x==0) return 0;
	if(visit[x]) return f[x];
	visit[x]=1;
	int s19=INF,s20=INF,s21=INF;
	int tem=0;
	if(x>=19)
	{
		s19=DP(x-19);
		s19+=mate19(x-19+1,x,tem);
		if(s19<f[x])
		{
			f[x]=s19;
			F[x]=F[x-19]+P[tem].s;
		}
	}
	if(x>=20)
	{
		s20=DP(x-20);
		s20+=mate20(x-20+1,x,tem);
		if(s20<f[x])
		{
			f[x]=s20;
			F[x]=F[x-20]+P[tem].s;
		}
	}
	if(x>=21)
	{
		s21=DP(x-21);
		s21+=mate21(x-21+1,x,tem);
		if(s21<f[x])
		{
			f[x]=s21;
			F[x]=F[x-21]+P[tem].s;
		}
	}
	return f[x];
}
void work()
{
	for(int i=1;i<=N;i++) f[i]=INF;
	DP(N);
	cout<<F[N]<<endl;
}
int main()
{
	freopen("charrec1.in","r",stdin);
	freopen("charrec1.out","w",stdout);
	read();
	work();
	return 0;
}