1055: [HAOI2008]玩具取名
Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 1560 Solved: 907
[Submit][Status][Discuss]
Description
Input
Output
Sample Input
II
WW
WW
IG
IIII
Sample Output
HINT
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的更多相关文章
-
BZOJ 1055 玩具取名(区间DP)
很显然的区间DP,定义dp[i][j][k], 如果dp[i][j][k]=1表示字符串[i,j]可以组成k字符. # include <cstdio> # include <cst ...
-
Bzoj 1055: [HAOI2008]玩具取名 (区间DP)
Bzoj 1055: [HAOI2008]玩具取名 (区间DP) 题目链接:https://www.lydsy.com/JudgeOnline/problem.php?id=1055 区间动态规划和可 ...
-
Bzoj 1055 玩具取名(区间DP)
题面 题解 字符很麻烦,不妨用数字代替(比如1代表'W') const char c[5] = {0, 'W', 'I', 'N', 'G'}; 接着,像这种两个子串可以合并成另一个子串的题可以考虑区 ...
-
BZOJ1055: [HAOI2008]玩具取名[区间DP]
1055: [HAOI2008]玩具取名 Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 1588 Solved: 925[Submit][Statu ...
-
BZOJ 1055 玩具取名
Description 某人有一套玩具,并想法给玩具命名.首先他选择WING四个字母中的任意一个字母作为玩具的基本名字.然后他会根据自己的喜好,将名字中任意一个字母用“WING”中任意两个字母代替,使 ...
-
bzoj1055玩具取名——区间DP
题目:https://www.lydsy.com/JudgeOnline/problem.php?id=1055 区间DP,注意初始化!! 因为没记忆化,TLE了一晚上,区间DP尤其要注意不重复递归! ...
-
bzoj1055: [HAOI2008]玩具取名(dp)
1055: [HAOI2008]玩具取名 题目:传送门 简要题意: 就是固定四个字母,给出这四个字母分别可以由哪两个字母组成,然后在给你一个字符串,要求把这个字符串还原成原始的四个字母的其中一个. 题 ...
-
BZOJ 1260&;UVa 4394 区间DP
题意: 给一段字符串成段染色,问染成目标串最少次数. SOL: 区间DP... DP[i][j]表示从i染到j最小代价 转移:dp[i][j]=min(dp[i][j],dp[i+1][k]+dp[k ...
-
BZOJ 2933([Poi1999]地图-区间Dp)
2933: [Poi1999]地图 Time Limit: 1 Sec Memory Limit: 128 MB Submit: 7 Solved: 7 [ Submit][ Status] ...
随机推荐
-
Type.IsContextful 说明
首先看MSDN的说明: 中文:获取一个值,通过该值指示 Type 在上下文中是否可以被承载. 英文:Gets a value indicating whether the Type can be ho ...
-
MySQL中自己不太常用的命令
一 更改表的信息 alter table students add primary key (stunum); 为已经创建好的表添加主键. alter语句不仅可以添加主键,还可以对已经创建好的表修改一 ...
-
详解Linux安装GCC方法
转载自:http://blog.csdn.net/bulljordan23/article/details/7723495/ 下载: http://ftp.gnu.org/gnu/gcc/gcc-4. ...
-
你被adblock坑过吗?
最近上线一个新版本,需要在导航增加一个app的下载入口(一个图片链接),然后经过了正常的原型图.设计.切图.上线的过程,一切都是那么顺利.上线之后,像往常一下会让产品进行确认,所有的调整和优化 ...
-
Mac下Jekyll安装
之前一直用Wordpress,虽然功能强大,各种插件各种bug,如果想弄个主题,折腾得要命.最近改用jekyll+gitHub免费空间.记录一下. 我用的是Mac,所以只讲述Mac下如何安装,Wind ...
-
9---PIP 管理工具的使用
Python 不仅有强大的内置模块,还提供强大的三方模块. 官方网站: https://pypi.python.org/pypi 要适用三方的模块需要使用pip管理工具. 1.在安装pip前,请确认w ...
-
VMware 虚拟机 Ubuntu 登录后蓝屏问题
问题起因 在一次下班收工时关闭虚拟机 Ubuntu,出现异常:关机好久没有完成,进而导致 VMware 软件卡死.后来强行杀死 VMware.第二天上班,启动 VMware 后开启 Ubuntu,输入 ...
-
数据结构(java版)学习笔记(三)——线性表之单链表
单链表的优点: 长度不固定,可以任意增删. 单链表的缺点: 存储密度小,因为每个数据元素,都需要额外存储一个指向下一元素的指针(双链表则需要两个指针). 要访问特定元素,只能从链表头开始,遍历到该元素 ...
-
MySQL5.7: Paging using Mysql Stored Proc
-- 查询外键 涂聚文 (Geovin Du) select concat(table_name, '.', column_name) as 'foreign key', concat(referen ...
-
有关python 函数参数
# def foo(x):# print(x)### foo(1)# foo('a')# foo({'a':2}) #形参与实参:# def foo(x,y): #x=1,y=2# return x+ ...