思路:建立有向图!对于输入的字符串 s[i] 和 s[j],dis[i][j] 表示字符串 s[j] 接在 s[i] 后面时的重叠部分的长度。用函数 con(i,j) 计算 dis[i][j] 的值(注意!dis[i][j] 不一定等于 dis[j][i]!)。在函数 con 中,我采用了 STL 的双端队列(deque),它可以从容器首位插入元素,并且支持==比较运算。然后再用 dfs 找最长路,把字符串 s[i] 和 s[j] 接起来产生的长度为 s[i] 的长度+s[j] 的长度-dis[i][j]。
特别注意!一开始我就被这个坑了!每个单词可以用2次!
代码:
至于 vjudge 上的 HRBUST – 1213,有多组数据。。。
所以一开始我蜜汁WA。。。
代码:
0 条评论