0

我正在尝试解决这个 spoj 问题 http://www.spoj.pl/problems/ZUMA

我找不到可能的 dp 状态。

有人可以指导我这个问题可能的 dp 状态。

4

1 回答 1

1

我已经在 SPOJ 中接受了这个问题。我的状态是，从位置到i等于元素。对于过渡，您应该考虑两种情况：jp

  1. 插入多少块，i就像你需要利用那块一样，然后我们会遇到同样的问题，但i+1考虑j
  2. 假设q前面元素的位置等于 in 中的块i。我们应该考虑从到解决问题i，q-1然后从q到j解决每一个问题q。
于 2012-09-12T22:41:47.697 回答