题意是说给你若干个单词，每个单词有一定的分数。如果一个字符串包含了某个单词就会得到该单词的分数，并且可以重复计算。让你输出一个长度不大于N并且分数最大的字符串，分数相等时选最短的，长度相等时选字典序最小的。
DP方程很容易想，就是最普通的自动机DP。麻烦的地方在于保证字典序，如果从上向下DP，要保存前缀，比较字典序每次要从开头开始比较，可以写出来但是比较麻烦。我是将模式串反过来建图的，这样等于从后向前生成字符串，分数相同时每次选择较小的字符就一定能生成字典序最小的字符串，但要注意当两字符相等时要向前比较直到可以分出字典序为止。
代码交上去跑了15ms，看statistic已经排在第五了，就是内存稍微多了一点。。。于是。。猥琐的把int改成了short，然后就跑到rank1去了。。嘿嘿。。
#include <stdio.h> #include <string.h> #define MAXN 1001 int cas,n,m,sc[101]; char s[101][11]; int next[MAXN][26],fail[MAXN],flag[MAXN],pos; char nc[MAXN]; int newnode(){ for(int i=0;i<26;i++)next[pos][i]=0; fail[pos]=flag[pos]=0; return pos++; } void insert(char *s,int sc){ int len=strlen(s),p=0; //将字符串反向插入 for(int i=len-1;i>=0;i--){ int k=s[i]-'a'; int &x=next[p][k]; p=x?x:x=newnode(); //nc记录这个位置的字符 nc[p]=s[i]; } //flag记录走到这一点的分数 flag[p]=sc; } int q[MAXN],front,rear; void makenext(){ q[front=rear=0]=0,rear++; while(front<rear){ int u=q[front++]; for(int i=0;i<26;i++){ int v=next[u][i]; if(v==0)next[u][i]=next[fail[u]][i]; else q[rear++]=v; if(u&&v){ fail[v]=next[fail[u]][i]; //注意更新节点的价值 flag[v]+=flag[fail[v]]; } } } } int d[51][MAXN]; int fath[51][MAXN]; int cmpfath(int now,int u,int v){ while(now>0){ if(nc[u]!=nc[v])return nc[u]<nc[v]; u=fath[now][u],v=fath[now][v]; now--; } return 0; } void dp(){ memset(d,-1,sizeof d); d[0][0]=0; for(int i=0;i<n;i++){ for(int u=0;u<pos;u++){ if(d[i][u]==-1)continue; for(int k=0;k<26;k++){ int v=next[u][k]; //如果从该节点走过来价值比当前价值更高 if(d[i+1][v]<d[i][u]+flag[v]){ fath[i+1][v]=u; d[i+1][v]=d[i][u]+flag[v]; //价值相等时比较字典序,一直向前比较直到不等 }else if(d[i+1][v]==d[i][u]+flag[v]){ if(cmpfath(i,u,fath[i+1][v]))fath[i+1][v]=u; } } } } //确定最终走到哪一格,价值优先,其次是长度 int st=-1,ans=-1; for(int i=0;i<=n;i++){ for(int u=0;u<pos;u++){ if(d[i][u]<=0)continue; if(ans==-1||d[i][u]>d[st][ans]){ st=i,ans=u; }else if(i<=st&&d[i][u]==d[st][ans]){ if(cmpfath(i,u,ans))st=i,ans=u; } } } //因为字符串是反过来的,要从后向前输出答案 if(ans==-1){ printf("\n"); }else{ for(int now=st,p=ans;now>0;p=fath[now][p],now--) printf("%c",nc[p]); printf("\n"); } } int main(){ scanf("%d",&cas); while(cas--){ scanf("%d%d",&n,&m); for(int i=0;i<m;i++)scanf("%s",s[i]); for(int i=0;i<m;i++)scanf("%d",&sc[i]); pos=0;newnode(); for(int i=0;i<m;i++){ insert(s[i],sc[i]); } makenext(); dp(); } return 0; }