当前位置:网站首页>HDU - 1501 zipper (memory deep search)
HDU - 1501 zipper (memory deep search)
2022-07-01 06:12:00 【Great intelligence】
Portal
The question : give 3 A string a,b,c, ask c Yes No a,b Results after interleaving , That is to say a,b Without changing the character order of ,a,b The length of the string is less than 200
analysis : If you search directly and deeply , Complexity is 2^200, So we need to use memorization , Space also relieves time , Mark the past situation . Record in the search a,b,c length ,c The length of is equal to ab Sum of length , therefore book[a][b] Represents the same situation , Mark the next time you get to this point return;
AC Code :
#include<bits/stdc++.h>
using namespace std;
int inf=0x3f3f3f3f;
int l1,l2,l3;
char a[210],b[210],c[420];
int book[210][210];
int flag;
void dfs(int t1,int t2,int t3)
{
if(t3==l3)
{
flag=1;
return;
}
if(book[t1][t2])
return;
book[t1][t2]=1;
if(a[t1]==c[t3])
dfs(t1+1,t2,t3+1);
if(b[t2]==c[t3])
dfs(t1,t2+1,t3+1);
}
int main()
{
int t;
scanf("%d",&t);
for(int i=1;i<=t;i++)
{
memset(book,0,sizeof(book));
flag=0;
scanf("%s",a);
scanf("%s",b);
scanf("%s",c);
l1=strlen(a);
l2=strlen(b);
l3=strlen(c);
dfs(0,0,0);
if(flag==1)
printf("Data set %d: yes\n",i);
else printf("Data set %d: no\n",i);
}
}
边栏推荐
- c# Xml帮助类
- Talking from mlperf: how to lead the next wave of AI accelerator
- OpenGL es: (2) relationship between OpenGL es, EGL and glsl
- Database problems, how to optimize Oracle SQL query statements faster and more efficient
- OpenGL es: (3) EGL, basic steps of EGL drawing, eglsurface, anativewindow
- kubeadm搭建kubenetes 集群(个人学习版)
- Call us special providers of personal cloud services for College Students
- 分布式锁实现
- TiDB单机模拟部署生产环境集群(闭坑实践,亲测有效)
- Smartinstantiationawarebeanpostprocessor of the extension point series determines which construction method to execute - Chapter 432
猜你喜欢
DHT11 temperature and humidity sensor
蚂蚁新村田头村变甜头村 让厦门灌口镇田头村变甜头村的特色农产品之一是
论文学习记录随笔 多标签之GLOCAL
Huluer app help
This is the necessary software for college students 𞓜 knowledge management
让厦门灌口镇田头村变“甜头”村的特色农产品之一是
Chip, an empire built on sand!
Dear pie users, I want to confess to you!
Diagramme dynamique Excel
TiDB单机模拟部署生产环境集群(闭坑实践,亲测有效)
随机推荐
机械臂速成小指南(六):步进电机驱动器
地宫取宝(记忆化深搜)
数据库问题,如何优化Oracle SQL查询语句更快,效率更高
SystemVerilog学习-10-验证量化和覆盖率
El tooltip in the table realizes line breaking display
利用百度地图查询全国地铁线路
Multi label lsml for essay learning records
How to add a gourd pie plate
Some errors encountered in MySQL data migration
Oracle sequence + trigger
相同区域 多源栅格数据 各个像元行列号一致,即行数列数相同,像元大小相同
srpingboot security demo
68 Cesium代码datasource加载czml
Make: g++: command not found
One of the characteristic agricultural products that make Tiantou village, Guankou Town, Xiamen into a "sweet" village is
LED lighting used in health lighting
el-table 动态表头渲染 固定第一列 高度问题
Through cooperation with the University of international trade, we can increase efficiency for college students
UOW of dev XPO comparison
Chip, an empire built on sand!