HDU 6170 Two strings 思维 DP-白红宇

HDU 6170 Two strings 思维 DP

阅读量：5938 次

发布时间：2019-06-19

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

　　题目链接： http://acm.hdu.edu.cn/showproblem.php?pid=6170

　　题目描述：两个字符串问是否匹配， '.'可以匹配任意字符， '*'可以使前一个数的出现次数成上一个自然数(0, 1, 2, 3........)

　　解题思路： DP， dp(i, j)表示A串匹配到j位， B串匹配到i位两个串是否匹配，转移方程再代码里有，参考Jaihk662的博客，注释在代码中

　　代码：

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                #define lson l, m, rt<<1#define rson m+1, r, rt<<1|1#define mem0(a) memset(a,0,sizeof(a))#define meminf(a) memset(a,-0x3f,sizeof(a))#define fi(n) for(i=0;i

View Code

　　思考：一开始想枚举直接判断了，结果很快就WA了，越到后面越复杂，心不细就不要枚举......我没想到这道题也能用DP做，真的是长见识了，看来对于DP still have a long way to go 啊...... 感觉暑假快结束了，自己到底有没有提高呢

转载于:https://www.cnblogs.com/FriskyPuppy/p/7413871.html

你可能感兴趣的文章