求LA3623 The best name for your baby的DP方程
Opened this issue · 1 comments
GoogleCodeExporter commented
网上好像木有题解...谢谢!
Original issue reported on code.google.com by yingsi...@gmail.com on 9 May 2013 at 1:05
GoogleCodeExporter commented
首先通过引入附加符号，把所有规则都改成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
- Changed state: Accepted