|
Posted on 2009-08-24 20:07 Uriel 阅读(303) 评论(0) 编辑 收藏 引用 所属分类: POJ 、 DP
写得很烦。。貌似是一类经典的DP一次过很开心。。虽然代码很恶心
/**//*Problem: 3073 User: Uriel Memory: 160K Time: 0MS Language: C++ Result: Accepted*/
#include<stdio.h> #include<string.h>
char a[][5]={"4","|3","(","|)","3","|=","6","#","|","_|","|<","|_","|\\/|", "|\\|","0","|0","(,)","|?","5","7","|_|","\\/","\\/\\/","><","-/","2"}; int i,len,dp[450],s; char spam[450],rsc[200];
int main() { while(1) { memset(rsc,0x00,sizeof(rsc)); scanf("%s",rsc); if(strcmp(rsc,"end")==0)break; len=strlen(rsc); memset(spam,0x00,sizeof(spam)); for(i=0;i<len;i++) { strcat(&spam[1],a[rsc[i]-'A']); } s=strlen(&spam[1]); memset(dp,0,sizeof(dp)); dp[0]=1; for(i=1;i<=s;i++) { if(i==1 &&(spam[i]=='4' || spam[i]=='3' || spam[i]=='6' || spam[i]=='#' || spam[i]=='|' || spam[i]=='0' || spam[i]=='5' || spam[i]=='7' || spam[i]=='2' || spam[i]=='(')) { dp[1]=1; continue; } else if(spam[i]=='4' || spam[i]=='3' || spam[i]=='6' || spam[i]=='#' || spam[i]=='|' || spam[i]=='0' || spam[i]=='5' || spam[i]=='7' || spam[i]=='2' || spam[i]=='(') { dp[i]=dp[i-1]; } else dp[i]=0; if((spam[i-1]=='|' && spam[i]=='3')||(spam[i-1]=='|' && spam[i]=='=')) { dp[i]+=dp[i-2]; } if((spam[i-1]=='_' && spam[i]=='|')||(spam[i-1]=='|' && spam[i]=='_')) { dp[i]+=dp[i-2]; } if((spam[i-1]=='|' && spam[i]==')')||(spam[i-1]=='|' && spam[i]=='<')) { dp[i]+=dp[i-2]; } if((spam[i-1]=='|' && spam[i]=='0')||(spam[i-1]=='|' && spam[i]=='?')) { dp[i]+=dp[i-2]; } if((spam[i-1]=='\\' && spam[i]=='/')||(spam[i-1]=='-' && spam[i]=='/')) { dp[i]+=dp[i-2]; } if(spam[i-1]=='>' && spam[i]=='<') { dp[i]+=dp[i-2]; } if(i>3 && spam[i-3]=='|' && spam[i-2]=='\\' && spam[i-1]=='/' && spam[i]=='|') { dp[i]+=dp[i-4]; } if(i>3 && spam[i-3]=='\\' && spam[i-2]=='/' && spam[i-1]=='\\' && spam[i]=='/') { dp[i]+=dp[i-4]; } if(i>2 && spam[i-2]=='|' && spam[i-1]=='\\' && spam[i]=='|') { dp[i]+=dp[i-3]; } if(i>2 && spam[i-2]=='(' && spam[i-1]==',' && spam[i]==')') { dp[i]+=dp[i-3]; } if(i>2 && spam[i-2]=='|' && spam[i-1]=='_' && spam[i]=='|') { dp[i]+=dp[i-3]; } } printf("%d\n",dp[s]); } return 0; }
|