注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

GreenCloudS

 
 
 

日志

 
 

BZOJ-1212: [HNOI2004]L语言(TRIE+DP)  

2014-02-16 11:38:00|  分类: oi,bzoj,dp,trie |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

题目:http://www.lydsy.com/JudgeOnline/problem.php?id=1212


trie上的DP,不知道AC自动机怎么弄这题。。。


代码:

#include <cstdio>

#include <algorithm>

#include <cstring>

 

using namespace std ;

 

#define maxn 1001000

#define check( ch ) ( ch >= 'a' && ch <= 'z' )

#define maxv 310

 

struct node {

    int child[ 26 ] ;

    bool flag ;

    node(  ) {

        flag = false ;

        memset( child , 0 , sizeof( child ) ) ;

    }

} T[ maxv ] ;

 

int n , m , V = 0 ;

 

int s[ maxn ] , len ;

 

void getstr(  ) {

    len = 0 ; int ch ;

    for ( ch = getchar(  ) ; ! check( ch ) ; ch = getchar(  ) ) ;

    s[ ++ len ] = ch - 'a' ;

    for ( ch = getchar(  ) ; check( ch ) ; ch = getchar(  ) ) s[ ++ len ] = ch - 'a' ;

}

 

int f[ 2 ][ maxv ] , k ;

 

int Dp(  ) {

    memset( f[ 0 ] , 0 , sizeof( f[ 0 ] ) ) , k = 0 ;

    int ans = 0 ;

    f[ 0 ][ 0 ] = 1 ;

    for ( int i = 0 ; i ++ < len ; ) {

        bool flag = true ;

        memset( f[ k ^ 1 ] , 0 , sizeof( f[ k ^ 1 ] ) ) ;

        for ( int j = 0 ; j <= V ; ++ j ) if ( f[ k ][ j ] ) {

            if ( T[ j ].child[ s[ i ] ] ) {

                flag = false ;

                f[ k ^ 1 ][ T[ j ].child[ s[ i ] ] ] = max( f[ k ^ 1 ][ T[ j ].child[ s[ i ] ] ] , f[ k ][ j ] + 1 ) ;

                if ( T[ T[ j ].child[ s[ i ] ] ].flag ) {

                    ans = max( ans , f[ k ^ 1 ][ T[ j ].child[ s[ i ] ] ] - 1 ) ;

                    f[ k ^ 1 ][ 0 ] = max( f[ k ^ 1 ][ 0 ] , f[ k ^ 1 ][ T[ j ].child[ s[ i ] ] ] ) ;

                }

            }

        }

        k ^= 1 ;

        if ( flag ) break ;

    }

    return ans ;

}

 

int main(  ) {

    scanf( "%d%d" , &n , &m ) ;

    while ( n -- ) {

        getstr(  ) ;

        int t = 0 ;

        for ( int i = 0 ; i ++ < len ; ) {

            if ( ! T[ t ].child[ s[ i ] ] ) T[ t ].child[ s[ i ] ] = ++ V ;

            t = T[ t ].child[ s[ i ] ] ;

        }

        T[ t ].flag = true ;

    }

    while ( m -- ) {

        getstr(  ) ;

        printf( "%d\n" , Dp(  ) ) ;

    }

    return 0 ;

}



  评论这张
 
阅读(2)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017