【BZOJ-1055】玩具取名 区间DP

时间:2022-06-27 15:15:51

1055: [HAOI2008]玩具取名

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 1560  Solved: 907
[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

Solution

区间DP

暴力转移就可以...就是比人家慢个10多倍罢了

f[l][r][k]表示[l,r]是否能压成k

然后枚举区间长度,枚举左端点,枚举WING,枚举WING的每种缩,枚举断点

总之就是暴力转移,然后就可以了

Code

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<map>
using namespace std;
char s[][][],S[],N[],c[];
map<char,int>mp;
bool f[][][];
int main()
{
scanf("%d%d%d%d",&N[],&N[],&N[],&N[]);
mp['W']=,mp['I']=,mp['N']=,mp['G']=;
c[]='W',c[]='I',c[]='N',c[]='G';
for (int i=; i<=; i++)
for (int j=; j<=N[i]; j++)
scanf("%s",s[i][j]+);
scanf("%s",S+); int len=strlen(S+);
for (int i=; i<=len; i++) f[i][i][mp[S[i]]]=;
for (int i=; i<=len; i++)
for (int j=; j<=len; j++)
if (j+i-<=len)
{
int L=j,R=j+i-;
for (int k=; k<=; k++)
for (int l=; l<=N[k]; l++)
for (int m=L; m<R; m++)
f[L][R][k]|=(f[L][m][ mp[ s[k][l][] ]] & f[m+][R][ mp[ s[k][l][] ]]);
}
for (int i=; i<=; i++) if (f[][len][i]) putchar(c[i]);
if (!f[][len][] && !f[][len][] && !f[][len][] && !f[][len][]) puts("The name is wrong!");
return ;
}

【BZOJ-1055】玩具取名 区间DP的更多相关文章

  1. BZOJ 1055 玩具取名&lpar;区间DP&rpar;

    很显然的区间DP,定义dp[i][j][k], 如果dp[i][j][k]=1表示字符串[i,j]可以组成k字符. # include <cstdio> # include <cst ...

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

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

  3. Bzoj 1055 玩具取名(区间DP)

    题面 题解 字符很麻烦,不妨用数字代替(比如1代表'W') const char c[5] = {0, 'W', 'I', 'N', 'G'}; 接着,像这种两个子串可以合并成另一个子串的题可以考虑区 ...

  4. BZOJ1055&colon; &lbrack;HAOI2008&rsqb;玩具取名&lbrack;区间DP&rsqb;

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

  5. BZOJ 1055 玩具取名

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

  6. bzoj1055玩具取名——区间DP

    题目:https://www.lydsy.com/JudgeOnline/problem.php?id=1055 区间DP,注意初始化!! 因为没记忆化,TLE了一晚上,区间DP尤其要注意不重复递归! ...

  7. bzoj1055&colon; &lbrack;HAOI2008&rsqb;玩具取名(dp)

    1055: [HAOI2008]玩具取名 题目:传送门 简要题意: 就是固定四个字母,给出这四个字母分别可以由哪两个字母组成,然后在给你一个字符串,要求把这个字符串还原成原始的四个字母的其中一个. 题 ...

  8. BZOJ 1260&amp&semi;UVa 4394 区间DP

    题意: 给一段字符串成段染色,问染成目标串最少次数. SOL: 区间DP... DP[i][j]表示从i染到j最小代价 转移:dp[i][j]=min(dp[i][j],dp[i+1][k]+dp[k ...

  9. BZOJ 2933&lpar;&lbrack;Poi1999&rsqb;地图-区间Dp&rpar;

    2933: [Poi1999]地图 Time Limit: 1 Sec   Memory Limit: 128 MB Submit: 7   Solved: 7 [ Submit][ Status] ...

随机推荐

  1. Type&period;IsContextful 说明

    首先看MSDN的说明: 中文:获取一个值,通过该值指示 Type 在上下文中是否可以被承载. 英文:Gets a value indicating whether the Type can be ho ...

  2. MySQL中自己不太常用的命令

    一 更改表的信息 alter table students add primary key (stunum); 为已经创建好的表添加主键. alter语句不仅可以添加主键,还可以对已经创建好的表修改一 ...

  3. 详解Linux安装GCC方法

    转载自:http://blog.csdn.net/bulljordan23/article/details/7723495/ 下载: http://ftp.gnu.org/gnu/gcc/gcc-4. ...

  4. 你被adblock坑过吗?

        最近上线一个新版本,需要在导航增加一个app的下载入口(一个图片链接),然后经过了正常的原型图.设计.切图.上线的过程,一切都是那么顺利.上线之后,像往常一下会让产品进行确认,所有的调整和优化 ...

  5. Mac下Jekyll安装

    之前一直用Wordpress,虽然功能强大,各种插件各种bug,如果想弄个主题,折腾得要命.最近改用jekyll+gitHub免费空间.记录一下. 我用的是Mac,所以只讲述Mac下如何安装,Wind ...

  6. 9---PIP 管理工具的使用

    Python 不仅有强大的内置模块,还提供强大的三方模块. 官方网站: https://pypi.python.org/pypi 要适用三方的模块需要使用pip管理工具. 1.在安装pip前,请确认w ...

  7. VMware 虚拟机 Ubuntu 登录后蓝屏问题

    问题起因 在一次下班收工时关闭虚拟机 Ubuntu,出现异常:关机好久没有完成,进而导致 VMware 软件卡死.后来强行杀死 VMware.第二天上班,启动 VMware 后开启 Ubuntu,输入 ...

  8. 数据结构(java版)学习笔记(三)——线性表之单链表

    单链表的优点: 长度不固定,可以任意增删. 单链表的缺点: 存储密度小,因为每个数据元素,都需要额外存储一个指向下一元素的指针(双链表则需要两个指针). 要访问特定元素,只能从链表头开始,遍历到该元素 ...

  9. MySQL5&period;7&colon; Paging using Mysql Stored Proc

    -- 查询外键 涂聚文 (Geovin Du) select concat(table_name, '.', column_name) as 'foreign key', concat(referen ...

  10. 有关python 函数参数

    # def foo(x):# print(x)### foo(1)# foo('a')# foo({'a':2}) #形参与实参:# def foo(x,y): #x=1,y=2# return x+ ...