hdu1501 动态规划-白红宇

hdu1501 动态规划

阅读量：4496 次

发布时间：2019-06-08

本文共 1687 字，大约阅读时间需要 5 分钟。

这题有两种解题思路，一个是记忆化搜索，一个是dp。

分别贴代码：

记忆化搜索：

#include
     
      #include
      
       #include
       
        #include
        #include
         
          char str[1000],a[300],b[300];int sum,flag;int hash[205][205];void dfs(int i,int j,int k){    if(flag)        return ;    if(k==sum)    {        flag=1;        return ;    }    if(hash[i][j])        return ;    hash[i][j]=1;    if(a[i]==str[k])        dfs(i+1,j,k+1);    if(b[j]==str[k])        dfs(i,j+1,k+1);}int main(){    int i,j,t,Case=1;    scanf("%d",&t);    while(t--)    {        scanf("%s %s %s",&a,&b,&str);        sum=strlen(str);        flag=0;        memset(hash,0,sizeof(hash));        dfs(0,0,0);        if(flag)            printf("Data set %d: yes\n",Case++);        else            printf("Data set %d: no\n",Case++);    }    return 0;}

dp：

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;int dp[205][205];int main(){    int i,j,l1,l2,sum,t,Case=1;    char a[205],b[205],str[405];    scanf("%d",&t);    while(t--)    {        scanf("%s%s%s",&a,&b,&str);        l1=strlen(a);        l2=strlen(b);        memset(dp,0,sizeof(dp));        dp[0][0]=1;        for(i=0;i<=l1;i++)            for(j=0;j<=l2;j++)            {                if(i>0&&a[i-1]==str[i+j-1]&&dp[i-1][j])                    dp[i][j]=1;                if(j>0&&b[j-1]==str[i+j-1]&&dp[i][j-1])                    dp[i][j]=1;            }        if(dp[l1][l2])            printf("Data set %d: yes\n",Case++);        else            printf("Data set %d: no\n",Case++);    }    return 0;}