动态规划问题 [英] A Dynamic programming problem

问题描述

谁能帮我找到一个最佳的动态规划算法这个问题

在途中吃饭，CCC的竞争者正在排队为他们的美味炸薯条。在N（1≤N≤100）的竞争对手已经排到了单文件进入食堂。

医生V时，谁运行CCC，实现了在程序员只是讨厌排队旁边谁使用不同语言的程序员的最后一分钟。值得庆幸的是，只有两种语言被允许在CCC：Gnold和帮助文件。此外，竞争对手已经决定，他们将只能进入食堂，如果他们在一组中的至少K（1≤ķ≤6）的竞争对手。

医生V决定迭代以下方案：

  *他会发现一组K或谁使用相同的语言站在旁边，彼此行并将它们发送到晚餐更多竞争对手。
*剩下的竞争对手将缩小差距，有可能将类似语言的竞争对手一起。
 

所以，医生V记录了你的竞争对手的顺序。所有的竞争对手可以用餐？如果是这样，什么是竞争者组被发送到吃饭的最低数量？ 输入

第一行包含两个整数N和K. 第二行有N个字符是一致的竞争对手序列（H再presents帮助文件，G重presents Gnold） 输出

输出，在一行中，单数，它是形成为晚餐该基团的最小数目。如果不是所有的程序员可以用餐，输出-1。

解决方案

我preFER不就解决了SPOJ问题，以务实的态度对你，所以采取以下作为一个多时间的存在性证明DP。

对K固定，一组可用餐的字符串是上下文无关。我将使用先按g 和 ^ h 而不是和 ^ h 。例如，在K = 3中，一个语法看起来像

 的S  - ＆GT; ε|克S-克S-克S- G | ^ h中文中文中文

摹 - ＆GT; ε|克S-摹

^ h  - ＆GT; ε| ^ h中文
 

的想法是，要么没有用餐者，或第一晚餐进餐与至少K - 其中（和最后和端）有可以用餐的字符串的1人，任何两个之间

现在使用 CYK 的加权变异找最小权重解析，其中非空小号作品有重量1，和所有其他有分量0对K固定，CYK的运行时间为O（N ³ ）。

Can anyone help me find an optimal Dynamic programming algorithm for this problem

On the way to dinner, the CCC competitors are lining up for their delicious curly fries. The N (1 ≤ N ≤ 100) competitors have lined up single-file to enter the cafeteria.

Doctor V, who runs the CCC, realized at the last minute that programmers simply hate standing in line next to programmers who use a different language. Thankfully, only two languages are allowed at the CCC: Gnold and Helpfile. Furthermore, the competitors have decided that they will only enter the cafeteria if they are in a group of at least K (1 ≤ K ≤ 6) competitors.

Doctor V decided to iterate the following scheme:

* 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.

So Doctor V recorded the sequence of competitors for you. Can all the competitors dine? If so, what is the minimum number of groups of competitors to be sent to dinner? Input

The first line contains two integers N and K. The second line contains N characters that are the sequence of competitors in line (H represents Helpfile, G represents Gnold) Output

Output, on one line, the single number that is the minimum number of groups that are formed for dinner. If not all programmers can dine, output -1.

解决方案

I'd prefer not to solve an SPOJ problem in a practical manner for you, so take the following as an existence proof of a poly-time DP.

For K fixed, the set of strings that can dine is context-free. I'm going to use g and h instead of G and H. For example, for K = 3, one grammar looks like

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

G -> ε | g S G

H -> ε | h S H

The idea is that either there are no diners, or the first diner dines with at least K - 1 others, between any two of which (and the last and the end) there is a string that can dine.

Now use the weighted variant of CYK to find the minimum-weight parse, where nonempty S productions have weight 1, and all others have weight 0. For K fixed, the running time of CYK is O(N³).

这篇关于动态规划问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！