动态编程问题

Question

任何人都可以帮我找到这个问题的最佳动态编程算法

在去吃饭的路上,CCC的竞争对手正在为他们美味的卷曲薯条排队.N(1≤N≤100)的竞争对手排队单一文件进入自助餐厅.

管理CCC的V博士在最后一刻意识到,程序员只是讨厌排在使用不同语言的程序员旁边.值得庆幸的是,CCC只允许使用两种语言:Gnold和Helpfile.此外,竞争对手已经决定,如果他们属于至少K(1≤K≤6)的竞争对手,他们将只进入自助餐厅.

V博士决定迭代以下方案:

* He will find a group of K or more competitors who use the same language standing next to each other in line and send them to dinner.
* The remaining competitors will close the gap, potentially putting similar-language competitors together.

因此,V博士为您记录了竞争对手的顺序.所有竞争对手都可以用餐吗？如果是这样,竞争对手的最低数量是多少？输入

第一行包含两个整数N和K.第二行包含N个字符,它们是行中的竞争者序列(H代表帮助文件,G代表Gnold)输出

在一行上输出单个数字,它是晚餐时形成的最小组数.如果不是所有程序员都可以用餐,输出-1.

Answer 1

我不希望以实际的方式为您解决SPOJ问题,因此请将以下内容作为多时间DP的存在证明.

对于K fixed,可以用餐的字符串集是无上下文的.我打算用g而h不是G和H.例如,对于K = 3,一个语法看起来像

S -> ? | g S g S g S G | h S h S h S H

G -> ? | g S G

H -> ? | h S H

这个想法是,要么没有食客,要么第一个用餐者至少有K-1个用餐,其中任何两个(以及最后和最后)之间都有一个可以用餐的字符串.

现在使用CYK的加权变量来找到最小权重解析,其中非空S产生权重为1,其他所有权重为0.对于K固定,CYK的运行时间为O(N ³).