基于TopCoder的生物训练动态规划
我一直在努力解决以下TopCoder问题
你正在玩一个战略游戏，你希望训练最强大的军队为最后的战斗。游戏中有N级生物，编号从0到N-1，包括在内.你已经有一些生物在你的军队和D天训练他们。你拥有的生物的数量是在int[]计数中给出的。它包含N个元素，它的第一个元素是一级生物的数量. 在每一天，你可以选择一个生物，并训练它。训练使生物的等级增加1，即0级的生物变成一级的生物，1级的生物变成2级的生物，以此类推。唯一的例外是一级生物--这类生物不能被训练，因为N-1是最大的可能等级。你可以在超过一天的时间里训练同一种生物。例如，如果你在3天内训练一个生物，它将获得3个等级。你也可以跳过那些日子，在那些日子里不训练任何生物。 你被赋予一个int[]的力量，其中第一个力量元素是一级生物的力量，你军队的力量是它所有生物的力量之和。在D天的训练结束后，把你的军队所能拥有的最大可能的力量还给你。
我无法得到算法。这是一个动态规划问题，我找不到合适的子问题来分解它。
有人能给我提供解决这个问题所需要考虑的子问题吗？
我也想知道你得出解决方案的思考过程。
回答 2
Stack Overflow用户
发布于 2013-06-25 10:44:35
Topcoder包括为他们的问题提供解决方案的社论。
这个问题的解决方案是这里
在如何进行升级方面，我们获得了完全的自由。在寻找最优算法时，自由是不好的-它给了我们太多的可能性去尝试。我们怎样才能限制搜索？ 我们可以决定系统地进行升级。我们将首先花费一些(可能为零)天来升级0级生物，然后升级一些一级生物，以此类推。显然，这样我们就能达到最优的总功率。(如果我们有一个以其他顺序进行升级的最佳解决方案，我们可以很容易地重新安排它们，并按我们的顺序进行。) 现在，我们可以轻松地编写一个递归解决方案，可以尝试所有的可能性。当然，我们想要回溯计算值，以避免指数时间复杂性。要做到这一点，我们需要精确地识别描述计算状态的内容。 有两个参数很明显:我们正在升级的生物的L级，以及所剩的天数D。然而，这并不是全部，还有一个更重要的问题。我们可能已经做了一些以前的升级，因此目前L级生物的数量可能高于输入值。这个差异将是第三个，也是最后一个参数。 最多有N=50级别，最多有D=100天。显然，第三个参数永远不会超过D，因此最多存在N*D*D=500,000状态。计算单个状态的时间复杂度为O(D)，从而导致整体时间复杂度O(N*D^3)。
long long memo[52][102][102];
long long counts[52], powers[52];
int N;
long long solve(int level, int add, long long upgrades) {
long long &res = memo[level][add][upgrades];
if (res >= 0) return res;
res = 0;
if (level==N) return res;
int maxUpgrades = min( upgrades, counts[level]+add );
for (int now=0; now<=maxUpgrades; now++) {
long long thisLevel = powers[level] * (counts[level]+add-now);
long long nextLevels = solve(level+1,now,upgrades-now);
res = max( res, thisLevel+nextLevels );
}
return res;
}
long long maximumPower(vector <int> _count, vector <int> _power, int D) {
memset(memo,-1,sizeof(memo));
N = _count.size();
for (int i=0; i<N; i++) counts[i] = _count[i];
for (int i=0; i<N; i++) powers[i] = _power[i];
return solve(0,0,D);
}Stack Overflow用户
发布于 2013-06-25 10:22:30
它看起来像个dp，很有趣，我很想试一试。我会以这样的方式对待它：
我创建一个等级之间的力量差异数组，然后追求升级低于该等级的生物，以获得我可以增加的最大力量。我认为这可能是一个贪婪或背包，因为哪些是升级是关键的决定。
编辑:我忘了提到你应该如何处理这个数组:你应该对它进行排序，以得到排序的索引。它实际上是一个映射，而不是数组，因为您希望在排序过程中对索引进行洗牌，这样您就可以知道哪些级别是最大的差异，正的还是负的。等
https://stackoverflow.com/questions/17294501
复制相似问题
腾讯云开发者
