动态规划问题

谁能帮我找到吃饭的最佳动态规划算法this problem 动态规划问题

在路上，在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. 第二行包含的在线（H表示帮助文件，G表示Gnold）竞争者输出

输出序列的N个字符，在一个线，这个单数是晚餐形成的最小组数。如果不是所有程序员都可以用餐，则输出-1。

来源

2011-03-04 GEP

如果你想得到一些答案，你应该适当地标记问题。 'trick'是一个非常无意义的标签。 – 2011-03-04 13:39:32

是的，我试图添加动态编程，但它拒绝它。 – GEP 2011-03-04 16:01:12

@kletoskletos - 这里有使用动态编程的理由吗？由于我们给出了Helpfile程序员的数量和Gnold程序员的数量，我们可以将他们的数字除以由Doctor V指定的组号码。其余的程序员需要被添加到已经组成的组中，吨超过六组。我想这就是动态编程发挥作用的地方。有趣的问题。 – 2011-03-04 17:10:57

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

对于固定的K，可以用餐的字符串集合是无上下文的。我将使用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加权变体以找到最小权重语法分析，其中非空小号制作具有权重1，并且所有其他具有重量0对K固定，CYK的运行时间为O（N 3 ）。

来源

2011-03-06 17:30:39 user635541

所以你说我可以使用一般版本的CYK算法在O（kN^3）时间内解决问题。 – GEP 2011-03-07 12:47:23

是的，在转换成乔姆斯基范式之后，语法的大小呈线性。 – user635541 2011-03-07 12:57:11

问题是我不知道乔姆斯基的正常形式是什么以及如何转换它。事实上，这是我第一次看到这个CYK算法，但它看起来非常类似于矩阵链乘法算法。实际上，我正在考虑一种算法，它可以找到每种可能的剩余食物的最优解，并将它们组合在一起。基础是矩阵链乘法算法，每个卵巢需要额外的O（n^2）时间，总共需要O（n^5）。您能否以自下而上的方式更好地描述您的算法？ – GEP 2011-03-07 19:43:51

该子问题是让每个人都能在特定状态下用餐的最小群体。有很多可能的行状态，但只有少数可以看到，所以你的记忆应该可以用散列图来完成。

这是一些伪代码。

int dine(string line){ 
    if(hashmap.contains(line)){ 
     return hashmap.get(line); 
    } 
    if(line.length == 0){ 
     return 0; 
    } 
    best = N+1; 
    for(i=0;i<line.length;i=j){ 
     type = string[i]; 
     j = i+1; 
     while(type == string[j]){ 
      j++; 
     } 
     if(j-i >= K){ 
      result = dine(string.substring(0,i-1) + string.substring(j,string.length)); 
      if(result > 0 && result < best){ 
        best = result; 
      } 
     } 
    } 
    if(best == N+1){ 
     hashmap.insert(line, -1); 
     return -1; 
    } 
    else { 
     hashmap.insert(line, best+1); 
     return best+1; 
    } 
}

如果您已经找到该行的答案，请返回该答案。如果队伍中没有人，你已经完成了，你不需要再组队。假设你不能组成任何组。然后尝试通过尝试所有连续组中相同想法的程序员来证明这个错误。如果这个群体足够大以便被选中，看看在删除这个群组后，需要多少更多的动作才能让每个人进入餐厅。跟踪所需的最少动作。

如果找不到删除所有组的方法，则返回-1。否则，在移除一个组加上一个之后，返回所需的最少移动，以说明您在此步骤中进行的移动。

来源

2011-03-04 17:10:14

你可以给你的解决方案的复杂性和一些更多的解释？ – GEP 2011-03-04 17:15:20

@dosdos对复杂性毫无头绪。 – 2011-03-04 17:33:14

我相信你的解决方案可以及时得到指数。 – GEP 2011-03-04 18:19:13

分而治之？在中间附近的某个地方采取一个（可移动的）组，并且两个组的任一侧，比如...... HHHGGGGGHHHHH .... - 现在有两种可能性。无论是那两组H用餐在同一组中，或者他们不用。如果他们在同一组中吃饭，那么他们之间的G必须作为一组正好那些G（所以你不妨尝试一下你的第一招）。如果他们不这样做，那么你可以分别解决左侧和右侧的子列表。无论是哪种情况，您都有一个较短的列表进行递归。

来源

2011-03-04 23:32:59

是的，但是这个算法的时间复杂度是多少？ – GEP 2011-03-05 00:20:26

我想或许一个更简单的方法是，您要标记每次移除的第一个和最后一个元素。我相信它有潜力成为指数型，但我不认为有任何解决方法（你可以构造一些最坏的情况下的序列），但希望你的竞争对手输入将是友好的:) – 2011-03-05 00:25:11

其实我正在开发一种算法像这样的矩阵链乘法。 – GEP 2011-03-05 01:00:20

动态规划问题

回答

相关问题