首页 > 代码库 > BZOJ 1055 HAOI2008 玩具取名 动态规划
BZOJ 1055 HAOI2008 玩具取名 动态规划
题目大意:给定一个由‘W‘,‘I‘,‘N‘,‘G‘构成的字符串。给定一些规则。这些规则能够将两个字符合成为一个,比如"II"能够合成为‘W‘,"WW"能够合成为‘I‘或者‘N‘
求这个字符串能够终于合成为哪几种字符
看到这题我想到了广搜。
。。事实上不是必需,动归全然能够解决
令f[i][j][k]为从i開始的j个字符能否够合成为字符[k]
然后j从外层循环。剩下的所有预处理,怎么暴力怎么转移。我写了六层循环,有点吓人
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define M 210 using namespace std; int n,W,I,N,G; int trans[4][4][4]; bool f[M][M][4],flag; char s[M],table[5]="WING"; inline int GetInt(char c) { switch(c) { case 'W':return 0; case 'I':return 1; case 'N':return 2; case 'G':return 3; } } inline void Input(int p) { int x,y; char c[2]; scanf("%s",c); x=GetInt(c[0]); y=GetInt(c[1]); trans[x][y][p]=1; } int main() { int i,j,k,c1,c2,c3; cin>>W>>I>>N>>G; for(i=1;i<=W;i++) Input(0); for(i=1;i<=I;i++) Input(1); for(i=1;i<=N;i++) Input(2); for(i=1;i<=G;i++) Input(3); scanf("%s",s+1); n=strlen(s+1); for(i=1;i<=n;i++) f[i][1][ GetInt(s[i]) ]=1; for(j=2;j<=n;j++) for(i=1;i+j-1<=n;i++) for(k=i;k<i+j-1;k++) for(c1=0;c1<4;c1++) if(f[i][k-i+1][c1]) for(c2=0;c2<4;c2++) if(f[k+1][i+j-1-k][c2]) for(c3=0;c3<4;c3++) if(trans[c1][c2][c3]) f[i][j][c3]=1; for(i=0;i<4;i++) if(f[1][n][i]) flag=1,putchar(table[i]); if(!flag) puts("The name is wrong!"); }
BZOJ 1055 HAOI2008 玩具取名 动态规划
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。