这道题,居然用错误的方法也可以AC,好吧,我看了比人写的代码,自己弄个数据进去了,好多wa了.
http://poj.org/problem?id=1699
题意是给你很多子序列,让你求最短父序列.
先说这道题的思路:
先预处理出来每两个子序列a,b,a添加到b后面最少添加多少个字符,并保存到add[a][b].
用dfs处理一下,枚举顺序,既然我们已经枚举顺序了,所以我们dfs的时候只需考虑b加到a后面就可以了,那a加到b后面的情况呢?因为是dfs所以肯定会遍历到,所以
我们只要默认添加在后面就好啦
为什么这样的算法可以呢?我一开始是感觉不可以的
以为这个是两两判断的所以......
阅读全文