Closed. This question needs to be more focused。它当前不接受答案。
想改善这个问题吗?更新问题,使其仅通过editing this post专注于一个问题。
4年前关闭。
我们有1个类型的N个硬币和2个类型的M个硬币。游戏板具有N个类型为1的正方形和M个类型为2的正方形。在这个游戏中,我们必须在每个方块中放入一个硬币。放置所有硬币后,我们将根据我们的硬币放置策略获得一个分数。
如果类型1的正方形包含1类硬币,那么我们将获得A点;如果类型2的正方形包含2类硬币,那么我们将获得B点;在所有其他情况下,我们将获得C点。分数将是所有平方的分数之和。
可用的用户输入为(N,M,A,B,C)
我们如何才能最大化得分?
例如,如果N = 3 M = 4 A = 500 B = 800 C = 600
通过最佳策略,我们将3个类型为1的硬币放入3个类型为1的正方形中获得分数= 500 + 500 + 500 = 1500,并将我们将2类型的2个硬币放入4个类型为2的正方形中得到分数= 800 + 800 + 800 + 800 = 3200,所以总成绩将为1500 + 3200 = 4700
想改善这个问题吗?更新问题,使其仅通过editing this post专注于一个问题。
4年前关闭。
我们有1个类型的N个硬币和2个类型的M个硬币。游戏板具有N个类型为1的正方形和M个类型为2的正方形。在这个游戏中,我们必须在每个方块中放入一个硬币。放置所有硬币后,我们将根据我们的硬币放置策略获得一个分数。
如果类型1的正方形包含1类硬币,那么我们将获得A点;如果类型2的正方形包含2类硬币,那么我们将获得B点;在所有其他情况下,我们将获得C点。分数将是所有平方的分数之和。
可用的用户输入为(N,M,A,B,C)
我们如何才能最大化得分?
例如,如果N = 3 M = 4 A = 500 B = 800 C = 600
通过最佳策略,我们将3个类型为1的硬币放入3个类型为1的正方形中获得分数= 500 + 500 + 500 = 1500,并将我们将2类型的2个硬币放入4个类型为2的正方形中得到分数= 800 + 800 + 800 + 800 = 3200,所以总成绩将为1500 + 3200 = 4700
最佳答案
这很简单。一种明显有效的解决方案是将所有1类硬币放置在1类正方形上。这会给你一定的分数。现在,我们可以将任何1类硬币替换为2类硬币。这样做,我们将失去A + B
的分数,但获得2 C
。因此,交换只有在2 C > A + B
时才有意义。我们可以交换min(N, M)
次。因此,最高分数是:
nSwaps =
if 2 * C > A + B then
min(N, M)
else
0
end if
maxScore = N * A + M * B + nSwaps * (2 * C - A - B)
关于c - 这个简单游戏的高效算法,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/31635246/