如何解决 spoj：SCALES - 平衡石头？

Question

这里是问题所在：SPOJ - SCALES

我在网上搜索过，在TopCoder and AoPS中找到了一些资料，但还是看不懂。请给我更多有关如何解决此问题的详细信息！

Answer 1

这是一个动态规划问题。

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

在i-th步骤中，您可以确定将重量为2^i-1的质量放在右边或左边或都不放左或右。但是如果W.[=19=的二进制表示的i-th位，你必须在左边再放一个2^i-1的质量]

第i步之后，你以后天平平衡只有两个条件：一个条件是天平现在平衡，另一个条件是左边是2ⁱ个多对吧

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

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];

如何解决 spoj：SCALES - 平衡石头？

How to solve spoj: SCALES - Balancing the Stone?

algorithm

dynamic-programming