分析：所有的文法都能拆分成A=S1S2这种形式,设状态f[i]j]表示字符i能生成的长度为j的字典序最小字符串,那么f[i][j] = min(f[k][j'] + f[l][j-j']),但是这样会有同层转移的情况,这种情况下状态之间会产生环,我们需要把这种情况拿出来特盘一下(单独跑一遍dij).
#include <bits/stdc++.h> using namespace std; typedef pair<string,int> pii; typedef pair<int,int> pi2; vector<pi2> G[600]; int n,l,cnt; bool vis[600][25],done[600]; char str[25]; string d[600],f[600][25]; priority_queue<pii,vector<pii>,greater<pii> > q; int main() { string INF = "~~"; while(scanf("%d%d",&n,&l) && (n+l)) { for(int i = 1;i <= 600;i++) G[i].clear(); cnt = 130; for(int i = 1;i <= n;i++) { scanf("%s",str); int n = strlen(str); if(n == 2) G[str[0]].push_back(make_pair(0,0)); else if(n == 3) G[str[0]].push_back(make_pair(str[2],0)); else if(n == 4) G[str[0]].push_back(make_pair(str[2],str[3])); else { G[str[0]].push_back(make_pair(str[2],++cnt)); for(int j = 3;j < n-2;j++) { G[cnt].push_back(make_pair(str[j],cnt+1)); cnt++; } G[cnt].push_back(make_pair(str[n-2],str[n-1])); } } for(int i = 0;i <= cnt;i++) for(int j = 0;j <= l;j++) f[i][j] = INF; memset(vis,0,sizeof(vis)); //状态是否可行 for(int i = 'A';i <= 'Z';i++) // l = 0的边界转移 for(pi2 v : G[i]) if(!(v.first + v.second)) { vis[i][0] = 1; f[i][0] = ""; } vis[0][0] = 1; for(char i = 'a';i <= 'z';i++) // l = 1的边界转移 { vis[i][1] = 1; f[i][1] = i; } for(int j = 0;j <= l;j++) { while(!q.empty()) q.pop(); for(int i = 0;i <= cnt;i++) d[i] = INF; memset(done,0,sizeof(done)); for(int i = 'A';i <= cnt;i++) { for(int k = 1;k < j;k++) for(pi2 v : G[i]) { if(vis[v.first][k] & vis[v.second][j-k]) { f[i][j] = min(f[i][j],f[v.first][k] + f[v.second][j-k]); vis[i][j] |= 1; } } if(vis[i][j]) { d[i] = f[i][j]; q.push(make_pair(d[i],i)); } } while(!q.empty()) { int u = q.top().second; q.pop(); if(done[u]) continue; done[u] = true; vis[u][j] = 1; f[u][j] = d[u]; for(int i = 'A';i <= cnt;i++) if(!done[i]) for(pi2 v : G[i]) if(v.first == u || v.second == u) { if(v.first == u && vis[v.second][0]) d[i] = d[u]; if(v.second == u && vis[v.first][0]) d[i] = d[u]; if(d[i] == d[u]) q.push(make_pair(d[i],i)); } } } if(!vis['S'][l]) { cout<<'-'<<endl; continue; } else cout<<f['S'][l]<<endl; } }
