search

wzcs11 / aoapc-book

Automatically exported from code.google.com/p/aoapc-book
0 stars 0 forks source link

求LA3623 The best name for your baby的DP方程 #20

Open GoogleCodeExporter opened 9 years ago

GoogleCodeExporter commented 9 years ago 
网上好像木有题解...谢谢!

Original issue reported on code.google.com by yingsi...@gmail.com on 9 May 2013 at 1:05

GoogleCodeExporter commented 9 years ago 
首先通过引入附加符号，把所有规则都改成A->BC这样的形式，
设f(i,L)表示初始为一个i, 通过规则得到一个长度为L的串, 
这个串字典序最小为多少, f(j,p)+f(k,L-p)转移到f(i,L), 
对应于规则i->jk, 
0<=p<=L。注意到p可以等于L，实际计算的时候得用类似dijkstra的
写法做状态转移

Original comment by rujia....@gmail.com on 19 May 2013 at 2:08