今天看了看这道在上尚未评定的题
虽说只是一道搜索题，可也不愧于他的尚未评定的难度
首先呢 各位对题意的理解可能是有一些偏差的
这道题可以重复使用同一个字符串！！！
设状态 dp[i][j] 表示 第 i 个字符串 还有长度为 j 的后缀未匹配，可以得到的最短答案。
考虑用记忆化搜索实现这个过程
if vis[i][j] 已经被走过了，说明形成了环路，接下来肯定就不应该被走了，直接return
if 已经有了dp[i][j] 则直接return dp[i][j] ,因为已经跑出了它的最优解了
在跑的同时,我们注意不断更新ans[i][j],并在ans相同时进行比较更换答案 否则就直接考虑更不更新
值得注意的是 对于所有的dp[n][i]=0 其余的dp值均为inf
这样就可以在到达最后有效情况时直接return了
代码我找的别人的，自己实在不想写了。。。
#includeusing namespace std;char wd[21][21]={0};int n=0,len[21]={0},dp[21][21]={0};char answ[21][21][200]={0};int vis[21][21]={0};inline bool judgex(int a,int b,int pa,int pb,int l){ for (int i=1;i<=l;i++) if (wd[a][pa+i-1]!=wd[b][pb+i-1]) return false; return true;}inline bool lex(int a,int b,int c,int d,int l){ for (int i=1;i<=l;i++) if (answ[a][b][i]!=answ[c][d][i]) return (answ[a][b][i]>answ[c][d][i]);}inline int minx(int now,int pos,int val,int p,int q){ if (val>2*1e9) return min(dp[now][pos],val); if ((dp[pos][now]==val&&lex(now,pos,p,q,dp[p][q])) || dp[now][pos]>val) { for (int i=1;i<=dp[p][q];i++) answ[now][pos][i]=answ[p][q][i]; for (int i=dp[p][q]+1;i<=val;i++) answ[now][pos][i]=wd[p][q+i-dp[p][q]]; } return min(dp[now][pos],val);}inline int _dp(int now,int pos){ if (dp[now][pos]!=2*1e9) return dp[now][pos]; for (int i=1;i<=n;i++) if (now!=i || pos!=len[i]) { if (len[i]<=pos && !vis[now][pos-len[i]] && judgex(now,i,pos-len[i]+1,1,len[i])) { vis[now][pos-len[i]]=1; dp[now][pos]=minx(now,pos,_dp(now,pos-len[i])+len[i],now,pos-len[i]); vis[now][pos-len[i]]=0; } if (len[i]>pos && !vis[i][len[i]-pos] && judgex(now,i,1,len[i]-pos+1,pos)) { vis[i][len[i]-pos]=1; dp[now][pos]=minx(now,pos,_dp(i,len[i]-pos)+pos,i,len[i]-pos); vis[i][len[i]-pos]=0; } } return dp[now][pos];}int main(){ scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%s",wd[i]+1),len[i]=strlen(wd[i]+1); for (int i=1;i<=20;i++) for (int j=1;j<=20;j++) dp[i][j]=2*1e9; int ans=2*1e9,p; for (int i=1;i<=n;i++) { vis[i][len[i]]=1; if (_dp(i,len[i])