BZOJ 1055 [HAOI2008]玩具取名

时间:2022-06-03 06:18:41

1055: [HAOI2008]玩具取名

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 1119  Solved: 653
[Submit][Status][Discuss]

Description

某人有一套玩具,并想法给玩具命名。首先他选择WING四个字母中的任意一个字母作为玩具的基本名字。然后他会根据自己的喜好,将名字中任意一个字母用“WING”中任意两个字母代替,使得自己的名字能够扩充得很长。现在,他想请你猜猜某一个很长的名字,最初可能是由哪几个字母变形过来的。

Input

第一行四个整数W、I、N、G。表示每一个字母能由几种两个字母所替代。接下来W行,每行两个字母,表示W可以用这两个字母替代。接下来I行,每行两个字母,表示I可以用这两个字母替代。接下来N行,每行两个字母,表示N可以用这两个字母替代。接下来G行,每行两个字母,表示G可以用这两个字母替代。最后一行一个长度不超过Len的字符串。表示这个玩具的名字。

Output

一行字符串,该名字可能由哪些字母变形而得到。(按照WING的顺序输出)如果给的名字不能由任何一个字母变形而得到则输出“The name is wrong!”

Sample Input

1 1 1 1
II
WW
WW
IG
IIII

Sample Output

IN

HINT

W可以变成II所以IIII可以缩成WW IN均能变成WW所以WW又可以缩成I或者N 所以最终答案应该按照“WING”的顺序输出IN

[数据范围]

100%数据满足Len<=200,W、I、N、G<=16

Source

题解:区间DP嘛,L~R用a组可不可以,每次用字典来分割区间。

又因为没有解的情况WA了一发= =。。。。。。。。

 #include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<cstring>
#define PAU putchar(' ')
#define ENT putchar('\n')
using namespace std;
const int maxn=+,inf=-1u>>;
int id(char ch){
if(ch=='W')return ;
if(ch=='I')return ;
if(ch=='N')return ;
if(ch=='G')return ;
return -;
}
void princ(int a){
if(!a)putchar('W');
else if(a==)putchar('I');
else if(a==)putchar('N');
else if(a==)putchar('G');
return;
}
int t[],tx[][][],arr[maxn];int dp[][maxn][maxn];
bool solve(int a,int L,int R){
int&res=dp[a][L][R];if(res!=-)return res;
if(L==R)return (res=(arr[L]==a));
for(int i=L;i<R;i++){
for(int j=;j<t[a];j++){
if(solve(tx[a][j][],L,i)&&solve(tx[a][j][],i+,R))return (res=true);
}
}return (res=false);
}
inline int read(){
int x=;bool sig=;char ch=getchar();
for(;!isdigit(ch);ch=getchar())if(ch=='-')sig=;
for(;isdigit(ch);ch=getchar())x=*x+ch-'';
return sig?x:-x;
}
inline void write(int x){
if(x==){putchar('');return;}if(x<)putchar('-'),x=-x;
int len=,buf[];while(x)buf[len++]=x%,x/=;
for(int i=len-;i>=;i--)putchar(buf[i]+'');return;
}
char s[maxn];
int main(){
for(int i=;i<;i++)t[i]=read();
for(int i=;i<;i++){
for(int j=;j<t[i];j++){
scanf("%s",s);tx[i][j][]=id(s[]);tx[i][j][]=id(s[]);
}
}
scanf("%s",s);
for(int i=;s[i];i++)arr[i]=id(s[i]);int Len=strlen(s);
memset(dp,-,sizeof(dp));bool flag=false;
for(int i=;i<;i++){
if(solve(i,,Len-))princ(i),flag=true;
}
if(!flag)puts("The name is wrong!");
return ;
}

BZOJ 1055 [HAOI2008]玩具取名的更多相关文章

  1. Bzoj 1055&colon; &lbrack;HAOI2008&rsqb;玩具取名 &lpar;区间DP&rpar;

    Bzoj 1055: [HAOI2008]玩具取名 (区间DP) 题目链接:https://www.lydsy.com/JudgeOnline/problem.php?id=1055 区间动态规划和可 ...

  2. bzoj 1055 &lbrack;HAOI2008&rsqb;玩具取名(区间DP)

    1055: [HAOI2008]玩具取名 Time Limit: 10 Sec  Memory Limit: 162 MBSubmit: 1258  Solved: 729[Submit][Statu ...

  3. &lbrack;BZOJ 1055&rsqb; &lbrack;HAOI2008&rsqb; 玩具取名 【记忆化搜索】

    题目链接:BZOJ - 1055 题目分析 这种类似区间 DP 的记忆化搜索都是很相近的,比如字符串压缩和字符串扩展都差不多. 都是将现在 Solve 的区间分成子区间,再求解子区间. 这道题 Sol ...

  4. &lbrack;BZOJ 1055&rsqb;&lbrack;HAOI2008&rsqb;玩具取名(DP)

    题目:http://www.lydsy.com:808/JudgeOnline/problem.php?id=1055 分析: 比较难想的dp f[i][j][c]表示i..j能否压缩成字符c 那么怎 ...

  5. BZOJ 1055&colon; &lbrack;HAOI2008&rsqb;玩具取名(记忆化搜索)

    http://www.lydsy.com/JudgeOnline/problem.php?id=1055 题意: 思路:记忆化搜索. #include<iostream> #include ...

  6. &lbrack;LUOGU&rsqb; P4290 &lbrack;BZOJ&rsqb; 1055 &lbrack;HAOI2008&rsqb;玩具取名

    题目描述 某人有一套玩具,并想法给玩具命名.首先他选择WING四个字母中的任意一个字母作为玩具的基本名字.然后他会根据自己的喜好,将名字中任意一个字母用"WING"中任意两个字母代 ...

  7. BZOJ 1055 HAOI2008 玩具取名 动态规划

    题目大意:给定一个由'W','I','N','G'构成的字符串.给定一些规则.这些规则能够将两个字符合成为一个,比如"II"能够合成为'W',"WW"能够合成为 ...

  8. bzoj 1055&colon; &lbrack;HAOI2008&rsqb;玩具取名【区间dp】

    不难想,就是处理起来比较麻烦 设f[i][j][k]为是否可以把区间(i,j)合并为k,初始状态是f[i][j][s[i]]=1,转移的话另一段枚举长度x,向(i-x,j),(i,j+x)转移 把四个 ...

  9. 【BZOJ】1055&colon; &lbrack;HAOI2008&rsqb;玩具取名(dp)

    http://www.lydsy.com/JudgeOnline/problem.php?id=1055 我竟然都没往dp这个方向想.....百度了下看到标题是dp马上就会转移了QAQ... 设d[i ...

随机推荐

  1. vps推荐之DigitalOcean

    作为一个爱折腾的网站”程序猿“,我用过多家vps,由于一般支持paypal 月付, 所以基本上都会用两三个月,不行就换另一家. 1.Yard VPS *人开的,有中文支持,貌似也支持支付宝付款,偶尔 ...

  2. Axis2在Web项目中整合Spring

    一.说明: 上一篇说了Axis2与Web项目的整合(详情 :Axis2与Web项目整合)过程,如果说在Web项目中使用了Spring框架,那么又改如何进行Axis2相关的配置操作呢? 二.Axis2 ...

  3. fastscript调用delphi方法和DELPHI调用FASTSCRIPT方法

    fastscript调用Delphi过程:  1. 先创建事件处理方法:TfsCallMethodEvent 2. 然后再用调用TfsScript.AddMethod方法,第一个参数为Delphi方法 ...

  4. smarty中的母板极制&lowbar;extends和block标签

    模板继承 继承是从面向对象编程而来的概念,模板继承可以让你定义一个或多个父模板,提供给子模板来进行扩展. 扩展继承意味着子模板可以覆盖部分或全部父模板的块区域. 继承结构可以是多层次的,所以你可以继承 ...

  5. android数据库sqlite增加删改查

    http://hi-beijing.iteye.com/blog/1322040 http://www.cnblogs.com/wenjiang/archive/2013/05/28/3100860. ...

  6. 基于百度地图SDK和Elasticsearch GEO查询的地理围栏分析系统(2)-查询实现

    在上一篇博客中,我们准备好了数据.现在数据已经以我们需要的格式,存放在Elasticsearch中了. 本文讲述如何在Elasticsearch中进行空间GEO查询和聚合查询,以及如何准备ajax接口 ...

  7. Python学习笔记 - 函数参数

    >>> def power(x): ... return x * x ... >>> power(5) 25 >>> def power(x, n ...

  8. &lbrack;物理学与PDEs&rsqb;第1章第6节 电磁场的标势与矢势 6&period;1 预备知识

    1.  若 ${\bf B}$ 为横场 ($\Div{\bf B}=0\ra {\bf k}\cdot {\bf B}=0\ra $ 波的振动方向与传播方向平行), 则 $$\bex \exists\ ...

  9. Gradle安装和在Eclipse中的使用

    Gradle是一个基于Apache Ant和Apache Maven概念的项目自动化构建开源工具.它使用一种基于Groovy的特定领域语言(DSL)来声明项目设置,抛弃了基于XML的各种繁琐配置. 1 ...

  10. O&lpar;N&rpar; 求数组中最大子串和

    int MaxSubSum3(int *arr, int len) { int i; long long MaxSum = 0; long long CurSum = 0; for(int i = 0 ...