2019年9月训练(贰)区间DP (luogu 4290)
2024-09-04 20:05:43
区间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;
之后选择比较好写的记忆化搜索去完成
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
最新文章
- Excel&mdash;&mdash;MATCH函数
- gslX680驱动的移植实践
- C# Math类简介
- scroll、offset和client的区别
- as(C# 参考)
- STL源码学习----lower_bound和upper_bound算法[转]
- Linux命令之cut
- python学习小结5:封装、继承、多态
- Windows 8 Hyper-V虚拟机功能(转载)
- 解决 jsp eclipse异常 【The import javax.servlet cannot be resolved】
- [置顶] block一点也不神秘————如何利用block进行回调
- Drupal7模块multiselect使用
- Cocos2d-x 文本渲染
- MYSQL 函数复习
- Linux--shell脚本之文本处理工具
- 【BZOJ5303】[HAOI2018]反色游戏(Tarjan,线性基)
- PHP Tp5.0 PHPExcel 导出操作
- Gitlab CR
- Linux 下查看局域网内所有主机IP和MAC
- [LeetCode] 747. Largest Number At Least Twice of Others_Easy