记录编号	82747	评测结果	AAAAAAAAA
题目名称	[IOI 1997][USACO]字符识别	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.201 s
提交时间	2013-11-26 21:19:21	内存使用	2.97 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>
#include<vector>
#include<cmath>
#include<algorithm>
#include<iomanip>
#include<deque>
using namespace std;
//文件格式为:从charrec.in中先输入字典,再输入数据
const int SIZEN=1210,SIZEW=23,SIZEC=28;
const int numc=27,imgw=20,INF=0x3fffffff;
const int MAXF=1200*20;
class CG{//字符图像
public:
	char rc;//真实的字符
	bool img[SIZEW][SIZEW];
	void output(void){//调试接口
		int i,j;
		for(i=1;i<=imgw;i++){
			for(j=1;j<=imgw;j++) cout<<img[i][j];cout<<endl;
		}
	}
	CG(){
		memset(img,0,sizeof(img));
	}
};
CG dict[SIZEC];//字典
int N;//文本行数
bool text[SIZEN][SIZEW]={0};//文本
int diff[SIZEN][SIZEC][SIZEW]={0};//文本第i行与第j个字符的第k行之差别
int f[SIZEN]={0};
char lastc[SIZEN]={0};//第i行为末尾,最优决策的该字符
int last[SIZEN]={0};//第i行为末尾,最优决策的上个决策位置
void answer(void){
	int x=N;
	deque<char> ans;
	while(x){
		ans.push_front(lastc[x]);
		x=last[x];
	}
	int i;
	for(i=0;i<ans.size();i++) cout<<ans[i];
	cout<<endl;
}
void relax_dcmode(int x){//以x结尾19行,更新最少改变
	int ans=INF,sum=0;
	int i,j;
	int btm=x-imgw+1;
	if(f[btm]>MAXF) return;
	for(i=1;i<=numc;i++){
		sum=f[btm];
		for(j=2;j<=imgw;j++) sum+=diff[btm+j-1][i][j];
		if(sum<f[x]){
			f[x]=sum;
			last[x]=btm;
			lastc[x]=dict[i].rc;
		}
		for(j=2;j<=imgw;j++){
			sum-=diff[btm+j-1][i][j];
			sum+=diff[btm+j-1][i][j-1];
			if(sum<f[x]){
				f[x]=sum;
				last[x]=btm;
				lastc[x]=dict[i].rc;
			}
		}
	}
}
void relax_kpmode(int x){//以x结尾20行,更新最少改变
	int i,j,ans=INF,sum;
	int btm=x-imgw;
	if(f[btm]>MAXF) return;
	for(i=1;i<=numc;i++){
		sum=f[btm];
		for(j=1;j<=imgw;j++) sum+=diff[btm+j][i][j];
		if(sum<f[x]){
			f[x]=sum;
			last[x]=btm;
			lastc[x]=dict[i].rc;
		}
	}
}
void relax_icmode(int x){//以x结尾21行,更新最少改变
	int i,j;
	int ans=INF,sum=0;
	int btm=x-imgw-1;
	if(f[btm]>MAXF) return;
	for(i=1;i<=numc;i++){
		sum=diff[btm+1][i][1]+f[btm];
		for(j=2;j<=imgw;j++) sum+=diff[btm+j+1][i][j];
		if(sum<f[x]){
			f[x]=sum;
			last[x]=btm;
			lastc[x]=dict[i].rc;
		}
		for(j=2;j<=imgw;j++){
			sum-=diff[btm+j+1][i][j];
			sum+=diff[btm+j][i][j];
			if(sum<f[x]){
				f[x]=sum;
				last[x]=btm;
				lastc[x]=dict[i].rc;
			}
		}
	}
}
void DP(void){
	int i;
	for(i=1;i<=N;i++) f[i]=INF;
	f[0]=0;
	for(i=imgw-1;i<=N;i++){
		if(i>=imgw-1){//19
			relax_dcmode(i);
		}
		if(i>=imgw){//20
			relax_kpmode(i);
		}
		if(i>=imgw+1){//21
			relax_icmode(i);
		}
	}
}
int linediff(bool x[],bool y[]){
	int i,sum=0;
	for(i=1;i<=imgw;i++) sum+=(x[i]!=y[i]);
	return sum;
}
void getdiff(void){
	int i,j,k;
	for(i=1;i<=N;i++){
		for(j=1;j<=numc;j++){
			for(k=1;k<=imgw;k++){
				diff[i][j][k]=linediff(text[i],dict[j].img[k]);
			}
		}
	}
}
void readform(bool s[][SIZEW],int n){//读n行
	int i,j;
	string str;
	for(i=1;i<=n;i++){
		cin>>str;
		for(j=1;j<=imgw;j++) s[i][j]=str[j-1]-'0';
	}
}
void read(void){
	int n;
	scanf("%d",&n);
	int i,j,k;
	string str;
	for(k=1;k<=numc;k++){
		if(k==1) dict[k].rc=' ';
		else dict[k].rc='a'+(k-2);
		readform(dict[k].img,imgw);
	}
	scanf("%d",&N);
	readform(text,N);
}
int main(){
	freopen("charrec1.in","r",stdin);
	freopen("charrec1.out","w",stdout);
	read();
	getdiff();
	DP();
	answer();
	return 0;
}