北京网站建设 招聘信息,大学培训中心网站建设,电子商务目前就业形势,石家庄市工程造价信息网题意#xff1a;给你n个模式串#xff0c;每个模式串有一个得分#xff0c;让你构造出一个长度为N之内且分数最高的文本串;输出字典序列最小的。 解题思路#xff1a; AC自动机 DP #xff0c; 不过要输出字典序列最小#xff0c;多开一个 一个三维字符串来辅助二维DP给你n个模式串每个模式串有一个得分让你构造出一个长度为N之内且分数最高的文本串;输出字典序列最小的。 解题思路 AC自动机 DP 不过要输出字典序列最小多开一个 一个三维字符串来辅助二维DP新思路 DP[i][j] ,表示到i位置状态为j的最大得分。 解题代码 1 // File Name: temp.cpp2 // Author: darkdream3 // Created Time: 2014年09月11日 星期四 15时18分4秒4 5 #includevector6 #includelist7 #includemap8 #includeset9 #includedeque10 #includestack11 #includebitset12 #includealgorithm13 #includefunctional14 #includenumeric15 #includeutility16 #includesstream17 #includeiostream18 #includeiomanip19 #includecstdio20 #includecmath21 #includecstdlib22 #includecstring23 #includectime24 #includequeue25 #define LL long long26 #define maxn 2000027 using namespace std;28 29 int n,m;30 char str[55][1110][55];31 struct Trie32 {33 int next[maxn][26],fail[maxn],end[maxn];34 int root,L;35 int newnode()36 {37 memset(next[L],-1,sizeof(next[L]));38 end[L] 0;39 return L-1;40 }41 void init()42 {43 L 0;44 root newnode();45 }46 void insert(char buf[],int id)47 {48 int len strlen(buf);49 int now root;50 for(int i 0;i len ;i)51 {52 if(next[now][buf[i]-a] -1)53 {54 next[now][buf[i]-a] newnode();55 }56 now next[now][buf[i]-a];57 }58 end[now] id;59 }60 void build()61 {62 queueintQ;63 fail[root] root;64 for(int i 0;i 26;i)65 if(next[root][i] -1)66 next[root][i] root;67 else68 {69 fail[next[root][i]] root;70 Q.push(next[root][i]);71 }72 while( !Q.empty() )73 {74 int now Q.front();75 Q.pop();76 if(end[fail[now]] -1)end[now] -1;77 else end[now] | end[fail[now]];78 for(int i 0;i 26;i)79 if(next[now][i] -1)80 next[now][i] next[fail[now]][i];81 else82 {83 fail[next[now][i]] next[fail[now]][i];84 Q.push(next[now][i]);85 }86 }87 }88 int cmp(char str1[],char str2[])89 {90 if(strlen(str1) strlen(str2))91 {92 return 1; 93 }else if(strlen(str1) strlen(str2)){94 return 0 ;95 }else{96 if(strcmp(str1,str2) 0)97 return 1;98 }99 return 0;
100 }
101 int dp[100][maxn];
102 void solve()
103 {
104 memset(dp,-1,sizeof(dp));
105 dp[0][0] 0 ;
106 int ai 0 ;
107 int aj 0 ;
108 int mx 0;
109 char tmp[55];
110 char ans[55];
111 strcpy(ans,);
112 strcpy(str[0][0],);
113 for(int i 0 ;i n;i )
114 {
115 for(int j 0 ;j L ;j )
116 {
117 if(dp[i][j] ! -1 )
118 {
119 strcpy(tmp,str[i][j]);
120 int len strlen(str[i][j]);
121
122 for(int s 0 ;s 26 ;s )
123 {
124 int nex next[j][s];
125 tmp[len] a s;
126 tmp[len 1] 0;
127 int tt dp[i][j];
128
129 if(end[nex] ! -1)
130 tt end[nex];
131
132 if(tt dp[i1][nex] ||(tt dp[i1][nex] cmp(tmp,str[i1][nex]) ))
133 {
134 dp[i1][nex] tt;
135 strcpy(str[i1][nex],tmp);
136 if(tt mx ||(tt mx cmp(tmp,ans)))
137 {
138 mx tt;
139 strcpy(ans,tmp);
140 //printf(%s %d\n,ans,mx);
141 }
142 }
143 }
144 }
145 }
146 }
147 printf(%s\n,ans);
148 }
149
150 };
151
152 Trie ac;
153 char tstr[205][20];
154 int main(){
155 int t;
156 scanf(%d,t);
157 while(t--)
158 {
159 scanf(%d %d,n,m);
160 ac.init();
161 for(int i 1;i m ;i )
162 {
163 scanf(%s,tstr[i]);
164 }
165 int temp ;
166 for(int i 1; i m;i )
167 {
168 scanf(%d,temp);
169 ac.insert(tstr[i],temp) ;
170 }
171 ac.build();
172 ac.solve();
173 }
174 return 0;
175 } View Code 转载于:https://www.cnblogs.com/zyue/p/3976079.html
