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

算法:区间dp;

这题是很简单的区间dp;(HA动规真不少)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<ctime>
#include<algorithm>
#include<cstdlib>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<cmath>
using namespace std;
#define FILE "dealing"
#define LL long long
#define up(i,j,n) for(int i=j;i<=n;i++)
#define pii pair<int,int>
#define piii pair<int,pii >
template<typename T> inline bool chkmin(T &a,T b){return a>b?a=b,true:false;}
template<typename T> inline bool chkmax(T &a,T b){return a<b?a=b,true:false;}
namespace IO{
char *fs,*ft,buf[<<];
inline char gc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,,<<,stdin),fs==ft))?:*fs++;}
inline int read(){
LL x=;int ch=gc();bool f=;
while(ch<''||ch>''){if(ch=='-')f=;ch=gc();}
while(ch<=''&&ch>=''){x=(x<<)+(x<<)+ch-'';ch=gc();}
return f?-x:x;
}
}using namespace IO;
namespace OI{
const int maxn();
char flag[];
int t[];
int f[][][];
int g[][][];
char s[];int n;
void init(){
flag[]='W',flag[]='I',flag[]='N',flag[]='G';
t['W']=,t['I']=,t['N']=,t['G']=;
int cnt[];
char ch[];
up(i,,)scanf("%d",&cnt[i]);
up(i,,)while(cnt[i]--){
scanf("%s",ch);
g[i][t[ch[]]][t[ch[]]]=;
}
scanf("%s",s+);
}
void slove(){
init();
n=strlen(s+);
up(i,,n)f[i][i][t[s[i]]]=;
int j;
up(L,,n)up(i,,n-L+){
j=i+L-;
up(k,i,(j-))up(t,,)up(x,,){
if(f[i][j][t])break;
up(y,,)if(f[i][k][x]&&f[k+][j][y]&&g[t][x][y]){f[i][j][t]=;break;}//转移比较暴力
}
}
bool f1=;
if(f[][n][]){cout<<"W";f1=;}
if(f[][n][]){cout<<"I";f1=;}
if(f[][n][]){cout<<"N";f1=;}
if(f[][n][]){cout<<"G";f1=;}
if(!f1)cout<<"The name is wrong!";
cout<<endl;
return;
}
}
int main(){
freopen(FILE".in","r",stdin);
freopen(FILE".out","w",stdout);
using namespace OI;
slove();
return ;
}

最新文章

  1. [WPF]建立自适应窗口大小布局的WinForm窗口
  2. Maven管理 划分模块
  3. Postgres数据库基本介绍
  4. 第四部分:python性能技巧
  5. reds pub/sub官方文档翻译
  6. C++ Union妙用(将列表初始化用于数组元素)
  7. 2016030201 - github上创建项目
  8. WPF中自定义绘制内容
  9. echarts绘制k线图为什么写candlestick类型就报错
  10. XSS简介
  11. react 组件列表
  12. Spring 的 AOP 进行事务管理的一些问题
  13. Python爬虫——selenium模块
  14. 源码编译安装nginx
  15. jq动态添加onclick事件在谷歌中不起作用
  16. 分享给大家一个500G.Net ftp资料库
  17. Eclipse新建工作空间,复制原有的配置
  18. eclipse zg项目学习
  19. Entity Framework Code First 遭遇主键自动生成问题
  20. 二、Web框架实现

热门文章

  1. Hibernate游记——盘缠篇(jar包)
  2. SpringBoot中@EnableAutoConfiguration注解用法收集
  3. docker run 报错——WARNING: IPv4 forwarding is disabled. Networking will not work.
  4. Android View源码解读:浅谈DecorView与ViewRootImpl
  5. 解决Sophos UTM 9防火墙上的“根分区填满”问题
  6. Maven plugin提示错误“Plugin execution not covered by lifecycle configuration”
  7. sklearn特征选择和分类模型
  8. php.ini的载入位置
  9. 配置Office Outlook 2013
  10. python(13)- 文件处理应用Ⅱ:增删改查