ZOJ2401 Zipper 双塔式 DP

时间:2022-04-01 08:52:34
第二次遇到双塔DP,再写一下。
(flag是为了避免memset多次导致的时间浪费)

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cstring>
using namespace std;
char x[],y[],z[];
int map[][],L,Lx;//410=210+x
bool _find(int flag)
{
for(int i=;i<=L;i++)
{
for(int j=;j<=min(Lx,i);j++)
if(map[i-][j]==flag)
{
if(j+<=min(Lx,i)&&x[j+]==z[i]) map[i][j+]=flag;
if(y[i-j]==z[i]) map[i][j]=flag;
}
}
if(map[L][Lx]==flag) return true;
return false;
}
int main()
{
int T;
cin>>T;
for(int i=;i<=T;i++)
{
map[][]=i;
scanf("%s",x+);
scanf("%s",y+);
scanf("%s",z+);
Lx=strlen(x+);
L=strlen(z+);
if(_find(i)) printf("Data set %d: yes\n",i);
else printf("Data set %d: no\n",i);
}
return ;
}