CODEWITHSUNDEEP
algorithmdynamic-programming
Tung
Tung

Reputation: 144

How to solve spoj: SCALES - Balancing the Stone?

Here is the problem: SPOJ - SCALES

I have searched on the web and found some information in TopCoder and AoPS but still cannot understand. Please give me some more details about how to solve this problem!

Upvotes: 1

Views: 929

Answers (1)

吴望龙
吴望龙

Reputation: 66

This is a dynamic-programming problem.

You can balance the scales by n steps.

In the i-th step, you can determine put the mass with weight 2i-1 to the right side or left or neither left nor right. But you must put another mass with 2i-1 to the left side if the i-th bit of the binary representation of W.

After the i-th step, you only have two conditions to balance the scales in the future: one condition is that the scales is balance now and another condition is that the left side is 2i units more than right.

Now we can design a dynamic-programming algorithm.

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

Upvotes: 5

Related Questions