2 7 2 love ever 5 5 5 1 ab 5
lovever ababHintSample 1: weight(love) = 5, weight(ever) = 5, so weight(lovever) = 5 + 5 = 10 Sample 2: weight(ab) = 2 * 5 = 10, so weight(abab) = 10
ac自动机+dp，要求把路径输出来，多开一维数组，记录每一个状态的路径，然后更新答案。
代码：
/* ***********************************************
Author :xianxingwuguan
Created Time :2014-2-5 13:02:53
File Name :3.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <string>
#include <time.h>
#include <math.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define INF 0x3f3f3f3f
#define eps 1e-8
#define pi acos(-1.0)
typedef long long ll;
int cmp(char *str1,char *str2){
int len1=strlen(str1);
int len2=strlen(str2);
if(len1!=len2)
return len1<len2;
return strcmp(str1,str2)<0;
}
char str[55][1100][55];
int dp[55][1100];
struct Trie{
int next[1200][26],fail[1200],end[1200];
int root,L;
int newnode(){
for(int i=0;i<26;i++)
next[L][i]=-1;
end[L++]=-1;
return L-1;
}
void init(){
L=0;
root=newnode();
}
void insert(char *str,int id){
int len=strlen(str);
int now=root;
for(int i=0;i<len;i++){
int p=str[i]-‘a‘;
if(next[now][p]==-1)
next[now][p]=newnode();
now=next[now][p];
}
end[now]=id;
}
void build(){
queue<int> q;
fail[root]=root;
for(int i=0;i<26;i++)
if(next[root][i]==-1)
next[root][i]=root;
else {
fail[next[root][i]]=root;
q.push(next[root][i]);
}
while(!q.empty()){
int now=q.front();
q.pop();
for(int i=0;i<26;i++)
if(next[now][i]==-1)
next[now][i]=next[fail[now]][i];
else {
fail[next[now][i]]=next[fail[now]][i];
q.push(next[now][i]);
}
}
}
void solve(int n){
for(int i=0;i<=n;i++)
for(int j=0;j<=L;j++)
dp[i][j]=-INF;
dp[0][0]=0;
char ans[110];strcpy(ans,"");
int Max=0;
strcpy(str[0][0],"");
for(int i=0;i<n;i++)
for(int j=0;j<L;j++)
if(dp[i][j]!=-INF){
int len=strlen(str[i][j]);
for(int k=0;k<26;k++){
char tmp[100];
strcpy(tmp,str[i][j]);
tmp[len]=‘a‘+k;tmp[len+1]=‘\0‘;
int tt=dp[i][j];
int pp=next[j][k];
if(end[pp]!=-1)tt+=end[pp];
if(tt>dp[i+1][pp]||(tt==dp[i+1][pp]&&cmp(tmp,str[i+1][pp]))){
dp[i+1][pp]=tt;
strcpy(str[i+1][pp],tmp);
if(dp[i+1][pp]>Max||(dp[i+1][pp]==Max&&cmp(str[i+1][pp],ans))){
strcpy(ans,str[i+1][pp]);
Max=dp[i+1][pp];
}
}
}
}
printf("%s\n",ans);
}
}ac;
char s[110][20];
int st[110];
int main()
{
//freopen("data.in","r",stdin);
//freopen("data.out","w",stdout);
int i,j,k,m,n,T;
scanf("%d",&T);
while(T--){
ac.init();
scanf("%d%d",&n,&m);
for(i=0;i<m;i++)scanf("%s",s[i]);
for(i=0;i<m;i++)scanf("%d",&st[i]);
for(i=0;i<m;i++)
ac.insert(s[i],st[i]);
ac.build();
ac.solve(n);
}
return 0;
}
原文：http://blog.csdn.net/xianxingwuguan1/article/details/18939175