区间DP

luogu 4290

明显的区间DP.

定义

dp[l][r][k]/*表示区间[l,r]能否凑成k(W,I,N,G)字符*/
mp['W']=1;mp['I']=2;mp['N']=3;mp['G']=4;

之后选择比较好写的记忆化搜索去完成

记录1  记录2  记录3

AC码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std; int na[],dp[][][],mp[],len;
char change[][][],toy[],h[]={' ','W','I','N','G'}; bool dfs(int l,int r,int k)
{
if(l==r) return toy[l]==h[k];//len<=1,不能换了
int& res=dp[l][r][k];
if(~res) return res;//11,12行这样更快,不会T掉,可以看上面的记录
for(int i=;i<=na[k];i++)
for(int j=l;j<r;j++)
if(dfs(l,j,mp[change[k][i][]])&&dfs(j+,r,mp[change[k][i][]]))
return res=;
return res=;
} int main()
{
memset(dp,-,sizeof(dp));
for(int i=;i<=;i++) scanf("%d",&na[i]);
for(int i=;i<=;i++)
{
for(int j=;j<=na[i];j++)
{
scanf("%s",&change[i][j]);
}
}
scanf("%s",toy+);
len=strlen(toy+);
bool flag=;
mp['W']=;mp['I']=;mp['N']=;mp['G']=;
for(int i=;i<=;i++)
if(dfs(,len,i))
{
flag=;
printf("%c",h[i]);
}
if(!flag) puts("The name is wrong!");
return ;
}

2019-09-19 22:22:05

最新文章

  1. Excel&mdash;&mdash;MATCH函数
  2. gslX680驱动的移植实践
  3. C# Math类简介
  4. scroll、offset和client的区别
  5. as(C# 参考)
  6. STL源码学习----lower_bound和upper_bound算法[转]
  7. Linux命令之cut
  8. python学习小结5:封装、继承、多态
  9. Windows 8 Hyper-V虚拟机功能(转载)
  10. 解决 jsp eclipse异常 【The import javax.servlet cannot be resolved】
  11. [置顶] block一点也不神秘————如何利用block进行回调
  12. Drupal7模块multiselect使用
  13. Cocos2d-x 文本渲染
  14. MYSQL 函数复习
  15. Linux--shell脚本之文本处理工具
  16. 【BZOJ5303】[HAOI2018]反色游戏(Tarjan,线性基)
  17. PHP Tp5.0 PHPExcel 导出操作
  18. Gitlab CR
  19. Linux 下查看局域网内所有主机IP和MAC
  20. [LeetCode] 747. Largest Number At Least Twice of Others_Easy

热门文章

  1. 【java设计模式】-05建造者模式
  2. HDFS 特殊权限位
  3. Leetcode题目101.对称二叉树(简单)
  4. JAVA单元测试的用法和要点
  5. laravel如何从mysql数据库中随机抽取n条数据
  6. vscode在软件内部查看html渲染效果的插件
  7. apache整合tomcat中的一些注意事项
  8. 机器学习 - 算法 - 集成算法 - 分类 ( Bagging , Boosting , Stacking) 原理概述
  9. selenium操作cookie
  10. Selenium 2自动化测试实战36(更易读的测试报告)