HDU 2296 DP + AC

题目    给你  N 个有价值的串，然后要你 在一个 长度 为  50 的字符组成的所有字符串里面 找到一个价值最大的串，如果，，，，，，，，

方法   反正就那样把！！ 可以考虑一个字符走到有价值串的末尾接着往下走，到根节点，如果根节点也进不去，那就没有什么用了，如果根节点进去了，当然也就会沿着字符往下走；这样不会影响到结果了；所以，，这样答案是对的， 至于 保存字符什么的，真的蛋疼死了，，，，，，，

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<cstring>
#define max(a,b) ((a)>(b)?(a):(b));
using namespace std;

struct date 
{
    date *next[26],*fail;
    int wi,in;
}tree[2500],*que[2500],*root;
int N,M,tail,head,total,val[120];
char path[55][1500][55],cha[120][12];

date *creat_node()
{
    for( int i = 0; i < 26; i++ )
    tree[total].next[i] = NULL;
    tree[total].fail    = NULL;
    tree[total].wi      = 0;
    tree[total].in      = total;
    return &tree[total++];
}

void inint( )
{
    tail = head = total = 0;
    root = creat_node();
    root->fail = root;
}

void insert( char *word,int wi )
{
    date *temp = root;
    while( *word )
    {
        int num = *word - 'a';
        if( temp->next[num] == NULL )
            temp->next[num] = creat_node();
        temp  = temp->next[num];
        word++;
    }
    temp->wi += wi;
}

void build_AC( )
{
    que[tail++] = root;
    while( tail > head )
    {
        date *temp = que[head++];
        for( int i = 0; i < 26; i++ )
        if( temp->next[i] != NULL )
        {
            if( temp == root ) temp->next[i]->fail = root;
            else               temp->next[i]->fail = temp->fail->next[i];
            temp->next[i]->wi += temp->next[i]->fail->wi;
            que[tail++] = temp->next[i];
        }
        else 
        {
            if( temp == root ) temp->next[i] = root;
            else               temp->next[i] = temp->fail->next[i];
        }
    }
}

int dp[55][1500];

void DP( )
{
   int i,j,k;
   memset( dp,-1,sizeof(dp) );
   dp[0][0] = 0;
   for( i = 0; i < N; i++ )
   for( j = 0; j < total; j++ )
   if( dp[i][j] != -1 )
   {
      for( k = 0; k < 26; k++ )
      {
         date *temp = tree[j].next[k];
         int wi = temp->wi;
         int in = temp->in;
         int len = strlen( path[i][j] );
         path[i][j][len] = (char)('a' + k );
         path[i][j][len+1] = '\0';
         if( dp[i][j] + wi > dp[i+1][in] )
         {
             dp[i+1][in] = dp[i][j] + wi;
               strcpy( path[i+1][in],path[i][j] );
         }
         else if( dp[i][j] + wi == dp[i+1][in] )
              if( strcmp( path[i+1][in],path[i][j] ) > 0 )
                     strcpy( path[i+1][in],path[i][j] );
         path[i][j][len] = '\0';
      }
   }
   int res = 0;
   for( i = 1; i <= N; i++ )
   for( j = 0; j < total; j++ )
       res = max( res,dp[i][j] );
   char str[55];str[0] = '!';
   for( i = 1; i <= N; i++ )
   for( j = 0; j < total; j++ )
   if( dp[i][j] == res && ( str[0] == '!' || strlen(path[i][j]) < strlen(str) || ( strlen(path[i][j]) == strlen(str) && strcmp(str,path[i][j]) > 0 ) ) )
                                                    strcpy( str,path[i][j] );
   if( res == 0 ) printf("\n");
   else           printf("%s\n",str);
}

int main( )
{
    int T,i;
    scanf("%d",&T);
    while( T-- )
    {
        inint( );
        scanf("%d%d",&N,&M);
        for( i = 1; i <= M; i++ )
            scanf("%s",&cha[i]);
        for( i = 1; i <= M; i++ )
            scanf("%d",&val[i]);
        for( i = 1; i <= M; i++ )
            insert( cha[i],val[i] );
        build_AC( );
        DP( );
    }
    return 0;
}