0

I have been trying to solve the following TopCoder problem:

You are playing a strategy game and you wish to train the strongest army for the final fight. There are creatures of N levels in the game, numbered from 0 to N-1, inclusive. You already have some creatures in your army and D days to train them. The number of creatures you have is given in a int[] count. It contains N elements and its i-th element is the number of creatures of level i.

During each day, you can choose one creature and train it. Training increases a creature's level by 1, i.e., a creature of level 0 becomes a creature of level 1, a creature of level 1 becomes a creature of level 2, and so on. The only exception is creatures of level N-1 - such creatures can't be trained as N-1 is the largest possible level. You can train the same creature during more than one day. For example, if you train a creature during 3 days, it will gain 3 levels. You can also skip days and not train any creatures during those days.

You are given a int[] power, where the i-th element of power is the power of one creature of level i. The power of your army is the sum of the powers of all its creatures. Return the maximum possible power your army can have after all D days of training are finished.

I'm not able to get the algorithm. It is a Dynamic Programming problem and I'm not able to find any suitable subproblem to which to break it to.

Can anyone provide me with the subproblem I need to consider to solve the problem?

I'd also like to know about the thinking process by which you arrive at the solution.

4

2 回答 2

1

Topcoder 包括为他们的问题提供解决方案的社论。

解决方案在这里：

我们在如何进行升级方面享有完全的自由。在寻找最佳算法时，自由是不好的——它给了我们太多尝试的可能性。我们如何限制搜索？

我们可以决定在进行升级时有点系统化。我们将首先花费一些（可能为零）天来升级 0 级生物，然后我们将升级一些 1 级生物，依此类推。显然，通过这种方式，我们将能够实现最优的总功率。（如果我们有一个按其他顺序进行升级的最佳解决方案，我们可以轻松地重新排列它们并按照我们的顺序进行。）

现在我们可以很容易地编写一个递归解决方案来尝试所有的可能性。当然，我们希望记住计算值以避免指数时间复杂度。为此，我们需要准确识别描述计算状态的内容。

两个参数是显而易见的：我们当前正在升级的生物的等级 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);
  }
于 2013-06-25T10:44:35.920 回答
0

它看起来像一个 dp，很有趣我很想尝试它.. 我会以这种方式接近它：

我创造了一系列不同等级之间的力量差异，然后追求升级低于该等级的生物以获得我可以添加的最大力量。我认为这可能是一个贪婪或背包，因为升级哪些是关键决定。

编辑：好吧，我忘了提到你应该用那个数组做什么：你应该对它进行排序以获得排序的索引..它实际上更像是一个地图而不是一个数组，因为你想在排序过程中打乱索引所以你可以知道哪些水平是最大的差异，积极或消极..等

于 2013-06-25T10:22:30.880 回答