noj 1066 poj 3073 spam 动态规划 .txt

ACM资料大集合

#include <stdio.h>
#include <iostream>
#include <math.h>
#include <algorithm>
#include <stdio.h>
#include <string.h>
using namespace std;
 
//NOJ 1066 POJ 3073 Spam 动态规划 
//动态规划不难想，字符串处理让人头大-。-，注意转义字符
#define NMAX 400
#define FMAX 27
#define KEYNUM sizeof(yfh)/sizeof(char *)

char* yfh[]={"4","|3","(","|)","3","|=","6","#","|","_|","|<","|_","|\\/|","|\\|","0","|0","(,)","|?","5","7","|_|","\\/","\\/\\/","><","-/","2"};
char* pxfh[]={"4","|3","(","|)","3","|=","6","#","|","_|","|<","|_","|\\/|","|\\|","0","|0","(,)","|?","5","7","|_|","\\/","\\/\\/","><","-/","2"};
int f[NMAX];
char zimu[NMAX];
char fuhao[NMAX];

int cmp(const void *a,const void *b)
{
	return strcmp((*(char * const *)a),(*(char * const *)b));
}

int cmps(const void *a,const void *b)
{
	char *ac=(char *)a;
	char **bc=(char **)b;
	return strcmp(ac,*bc);
}

int search(char *s)
{
	char **p;
	p=(char **)bsearch(s,pxfh,KEYNUM,sizeof(char *),cmps);
	if(p==NULL) return -1;
	else return p-pxfh;
}
void init()
{
	int i;
//	for(i=0;i<26;i++) printf("%s\n",pxfh[i]);
	qsort(pxfh,KEYNUM,sizeof(char *),cmp);
//	for(i=0;i<26;i++) printf("%s\n",pxfh[i]);
}

int trans(int num)
{	//把字母翻译成字符
	int i,k=0,j;
	char temp[5];
	for(i=0;i<num;i++)
	{
		strcpy(temp,yfh[zimu[i]-'A']);
		for(j=0;j<strlen(yfh[zimu[i]-'A']);)
		{
			fuhao[k++]=temp[j++];
		}
	}
	fuhao[k]='\0';
//	printf("fuhao=%s\n",fuhao);
	return k;
}

int max(int a,int b)
{
	if(a<b) return b;
	else return a;
}
int cal(int num)
{
	int i,j,sum,k,m;
	char str[5];
	for(i=0;i<=num;i++) f[i]=0;
//	system("pause");
	for(i=0;i<num;i++)
	{
		for(j=max(i-3,0);j<=i;j++)
		{
			m=0;
			for(k=j;k<=i;k++)
				str[m++]=fuhao[k];
			str[m]='\0';
//			if(i==0) printf("str=%s\n",str);
			if(search(str)!=-1) 
			{	//如果末字符串有对应
				//f[i]=f[i-4]*b4+f[i-3]*b3+f[i-2]*b2+f[i-1]*b1,(bj=1 iff fuhao[i-j+1,i-j+2...i]有意义) 
				if(j==0) f[i+1]++;//末字符串就是本身，则本身+1
				else f[i+1]+=f[j];//否则加上末字符串之前那一位的f[]
			}
		}
//		printf("f[%d]=%d\n",i+1,f[i+1]);
	}
//	for(i=1;i<=num;i++) printf("f[%d]=%d\n",i,f[i]);
	return f[num];
}
int main()
{
	init();
	scanf("%s",&zimu);
	while(strcmp(zimu,"end")!=0)
	{
		printf("%d\n",cal(trans(strlen(zimu))));
		scanf("%s",&zimu);
	}
	return 0;
}