Rescue the Rabbit (ZOJ Problem Set - 3545)

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3545

問題

n個の文字列siが良いDNAとして重みwiを持っている。長さlの遺伝子の良さはその遺伝子がsubstringとして含んでいる文字列のwiの合計となる。遺伝子の良さの最大値を求めよ。
1<=n<=10
1<=l<=100

wi

<=100

解法

良いDNAに対してAhoCorasickでPMAを作りそのオートマトン上でbit dp(bfs)を行う。状態の管理をsetを使って行うと間に合わないので注意。