Home > Old Blog Posts > USACO 5.4.3 Character Recognition

USACO 5.4.3 Character Recognition


这应该是USACO最不像DP的DP了。这是啥类型,统计DP?
设f[i]为前i行匹配的最小差距值,对应的字符串可以在求f[i]时求得
则f[i]=min(f[i-19]+cmp[i,19],f[i-20]+cmp[i,20],f[i-21]+cmp[i,21])
其中求cmp[i,j]:
若j=20,显然这时刚好匹配,只要直接计算就行了
若j=19,枚举添加的那一行,取差距最小的
若j=21,枚举删除的那一行,取差距最小的
由于每行20个字符,可以在读入时用整型变量压缩存储,计算a与b的差距值即计算a xor b的1的个数,对提速有一定的效果

/*
ID: dementr1
PROG: charrec
LANG: C++
*/
#include
#include
#define MAX 100000
using namespace std;
ifstream fin("charrec.in");
ifstream font("font.in");
ofstream fout("charrec.out");
int n,N;
int text[30][30]={};
int s[2000]={};
int f[2000];
string symbol[2000];
char word[27];
bool vis[2000]={false};
void init()
{
	char tmp;
	word[0]=' ';
	for(int i=1;i>N;
	for(int i=0;i<=26;i++)
		for(int j=1;j<=20;j++)
			for(int k=1;k>tmp;
				text[i][j]=(text[i][j]<>n;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j>tmp;
			s[i]=(s[i]<<1)+tmp-'0';
		}
	}
	for(int i=1;i>1)&0x55555555);
	x=(x&0x33333333)+((x>>2)&0x33333333);
	x=(x&0x0F0F0F0F)+((x>>4)&0x0F0F0F0F);
	x=(x&0x00FF00FF)+((x>>8)&0x00FF00FF);
	x=(x&0x0000FFFF)+((x>>16)&0x0000FFFF);
	return x;
}
int compare(int from, int length, int id)
{
	int ans=0;
	if(length==20)
	{
		for(int i=from;i<from+length;i++)
			ans+=cmp(s[i],text[id][i-from+1]);
		return ans;
	}
	if(length==19)
	{
		ans=MAX;
		for(int i=1;i<=20;i++)
		{
			int now=0;
			int a=1;
			for(int j=1;j<=20;j++)
			{
				if(i!=j)
				{
					now+=cmp(s[from+a-1],text[id][j]);
					a++;
				}
			}
			if(now<ans)
				ans=now;
		}
		return ans;
	}
	if(length==21)
	{
		ans=MAX;
		for(int i=1;i<=21;i++)
		{
			int now=0;
			int a=1;
			for(int j=1;j<=21;j++)
			{
				if(j!=i)
				{
					now+=cmp(s[from+j-1],text[id][a]);
					a++;
				}
			}
			if(now<ans)
				ans=now;
		}
		return ans;
	}
}
void dp(int h)
{
	vis[h]=true;
	if(0<=h&&h=19)
	{
		if(!vis[h-19])
			dp(h-19);
		if(f[h-19]!=MAX)
			for(int i=0;i<=26;i++)
			{
				tmp=compare(h-18,19,i)+f[h-19];
				if(tmp=20)
	{
		if(!vis[h-20])
			dp(h-20);
		if(f[h-20]!=MAX)
			for(int i=0;i<=26;i++)
			{
				tmp=compare(h-19,20,i)+f[h-20];
				if(tmp=21)
	{
		if(!vis[h-21])
			dp(h-21);
		if(f[h-21]!=MAX)
			for(int i=0;i<=26;i++)
			{
				tmp=compare(h-20,21,i)+f[h-21];
				if(tmp240)
		symbol[h][symbol[h].length()-1]='?';
}
void work()
{
	int tmp;
	string empty="";
	if(f[n]==MAX)
		dp(n);
}
void print()
{
	fout<<symbol[n]<<endl;
}
int main()
{
	init();
	work();
	print();
	return 0;
}



Categories: Old Blog Posts
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: