当前位置:网站首页>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);
}
}
边栏推荐
- Flink实战--多流合并
- LED lighting used in health lighting
- 基于LabVIEW的计时器
- [note] e-commerce order data analysis practice
- Ant new village is one of the special agricultural products that make Tiantou village in Guankou Town, Xiamen become Tiantou village
- Geoffrey Hinton: my 50 years of in-depth study and Research on mental skills
- FPGA - 7系列 FPGA内部结构之Clocking -02- 时钟布线资源
- uniapp树形层级选择器
- three. JS summary
- kotlin位运算的坑(bytes[i] and 0xff 报错)
猜你喜欢
kotlin位运算的坑(bytes[i] and 0xff 报错)
Seven major technical updates that developers should pay most attention to on build 2022
Small guide for rapid completion of mechanical arm (VI): stepping motor driver
CJC8988带2个立体声耳机驱动器的低功率立体声编解码器
jdbc 数据库操作
My experience from technology to product manager
无限水平大理石游戏
What if the data in the cloud disk is harmonious?
Why use huluer pie disk instead of U disk?
论文学习记录随笔 多标签之LSML
随机推荐
浏览器端保存数据到本地文件
Preliminary level of C language -- selected good questions on niuke.com
In win10 and win11, the scroll direction of Elan touch panel is reversed, and "double finger click to open the right-click menu" and "double finger scroll" are started“
3D printer threading: five simple solutions
Dear pie users, I want to confess to you!
MongoDB:一、MongoDB是什么?MongoDB的优缺点
kotlin位运算的坑(bytes[i] and 0xff 报错)
excel动态图表
HDU - 1501 Zipper(记忆化深搜)
One of the characteristic agricultural products that make Tiantou village, Guankou Town, Xiamen into a "sweet" village is
ONEFLOW source code parsing: automatic inference of operator signature
Using Baidu map to query national subway lines
Oracle create user + Role
Make: g++: command not found
OpenGL es: (4) detailed explanation of EGL API (Continued)
C# ManualResetEvent 类的理解
DEV XPO对比之XAF BO
uniapp树形层级选择器
Fixed height of the first column in El table dynamic header rendering
C language beginner level - realize the minesweeping game