[hdu2296]Ring(AC自动机+dp)

题意：你M个单词构成一个词典，每个单词有一个权值(单词出现多次算多个权值)，现在要你构造一个不超过长度N的字符串，使得该字符串权值最大。如果出现多个答案，输出最短的，如果依然有多解,输出字典序最小的。

解题关键：最典型的AC自动机上跑dp。

令$dp[i][j] = x$表示走了i步到达j点的最大价值，则

转移方程：$dp[i][j] = max (dp[i][j],dp[i-1][k] + val[j])$

$val[i]$代表以某前缀的价值总和。

注意这里是多对多的关系，需用从遍历起点时更新后面的点。

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 #include<cstdlib>
  5 #include<cstring>
  6 #include<iostream>
  7 #include<queue>
  8 #include<string>
  9 using namespace std;
 10 typedef long long ll;
 11 const int N=26;
 12 const int MAXN=1101;
 13 int m,n;
 14 int mod=100000;
 15 int val[MAXN];
 16 int dp[52][1101];
 17 string path[52][1101];
 18 struct Trie{
 19     int Next[MAXN][N],Fail[MAXN],root,tot;
 20     int End[MAXN];
 21     int newnode(){
 22         for(int i=0;i<N;i++) Next[tot][i]=-1;
 23         End[tot++]=0;
 24         return tot-1;
 25     }
 26     void init(){
 27         tot=0;
 28         root=newnode();
 29     }
 30     
 31     void insert(char buf[],int x){
 32         int len=(int)strlen(buf),now=root,k;
 33         for(int i=0;i<len;i++){
 34             k=buf[i]-'a';
 35             if(Next[now][k]==-1)  Next[now][k]=newnode();
 36             now=Next[now][k];
 37         }
 38         End[now]=x;
 39     }
 40     
 41     void build(){
 42         queue<int>que;
 43         Fail[root]=root;
 44         for(int i=0;i<N;i++){
 45             if(Next[root][i]==-1) Next[root][i]=root;
 46             else{
 47                 Fail[Next[root][i]]=root;
 48                 que.push(Next[root][i]);
 49             }
 50         }
 51         while(!que.empty()){
 52             int now=que.front();
 53             que.pop();
 54                End[now]+=End[Fail[now]];//此题可重复计算，所以要加
 55             for(int i=0;i<N;i++){
 56                 if(Next[now][i]==-1) Next[now][i]=Next[Fail[now]][i];
 57                 else{
 58                     Fail[Next[now][i]]=Next[Fail[now]][i];
 59                     que.push(Next[now][i]);
 60                 }
 61             }
 62         }
 63     }
 64     
 65     void solve(int n){
 66         memset(dp,-1,sizeof dp);
 67         dp[0][0]=0;
 68         for(int i=0;i<n;i++){
 69             for(int j=0;j<tot;j++){
 70                 if(dp[i][j]==-1) continue;
 71                 for(int k=0;k<26;k++){
 72                     int u=Next[j][k];
 73                     if(dp[i][j]+End[u]>dp[i+1][u]){
 74                         dp[i+1][u]=dp[i][j]+End[u];
 75                         path[i+1][u]=path[i][j]+char(k+'a');
 76                     }else if(dp[i][j]+End[u]==dp[i+1][u]){
 77                         string str=path[i][j];
 78                         str+=char(k+'a');
 79                         if(str<path[i+1][u]) path[i+1][u]=str;
 80                     }
 81                 }
 82             }
 83         }
 84         int ans=0,length=-1;
 85         for(int i=0;i<=n;i++){
 86             for(int j=0;j<tot;j++){
 87                 if(dp[i][j]>ans){
 88                     ans=dp[i][j];
 89                     length=i;
 90                 }
 91             }
 92         }
 93         if(ans==0){
 94             printf("
");
 95             return;
 96         }
 97         string str="";
 98         for(int j=0;j<tot;j++){
 99             if(dp[length][j]==ans&&(str>path[length][j]||str=="")) str=path[length][j];
100         }
101         printf("%s
",str.c_str());
102         //printf("%d
",ans);
103     }
104     
105 };
106 
107 Trie ac;
108 char buf[101][15];
109 int main(){
110     int T;
111     scanf("%d",&T);
112     while(T--){
113         ac.init();
114         scanf("%d%d",&n,&m);
115         for(int i=1;i<=m;i++){
116             scanf("%s",buf[i]);
117         }
118         for(int i=1;i<=m;i++) scanf("%d",val+i),ac.insert(buf[i],val[i]);
119         ac.build();
120         ac.solve(n);
121     }
122 }