algorithm - spoj : SCALES - Balancing the Stone?如何解决

Question

这里是问题所在:SPOJ - SCALES

我在网上搜索了一下，在TopCoder找到了一些资料和 AoPS但仍然无法理解。请给我更多有关如何解决此问题的详细信息!

Answer 1

这是一个动态规划问题。

您可以通过 n 步来平衡天平。

在第i-th步，你可以确定放置重量为2i-1的质量向右或向左或既不向左也不向右。但是如果 i-th 位，则必须在左侧放置另一个 2i-1 W 的二进制表示。

第i步之后，你以后要平衡天平只有两个条件:一个条件是天平现在平衡，另一个条件是左边是2< sup>i 个单位比对。

现在我们可以设计一个动态规划算法。

dp[i][0]: means after the i-th step the scales is balanced.

dp[i][1]: means after the i-th step the left side of the scales is 2^i units more than right.

If s[i] == 0
    dp[i][0] = dp[i-1][0] + dp[i-1][1];
    dp[i][1] = dp[i-1][1];
else
    dp[i][0] = dp[i-1][0];
    dp[i][1] = dp[i-1][0] + dp[i-1][1];