《建造基地》题目分析

题目链接

《建造基地》是offer收割编程练习赛1的第三题。本题本质上是一个略有变化的背包问题，旨在考察对背包、DP的理解和灵活运用。

首先根据题意我们知道基地的N级都是独立的。换句话说我们只须分别求出建第一级、第二级、…… 第N级的最小成本，然后把成本加起来即可。

当我们建设第c级基地的时候，我们有M种重金属（物品），第i种的成本（重量）是A[i], 建设值（价值）是B[i]/(T^(c-1))。

因为每种重金属可以使用无限次，所以这是一个完全背包问题。只不过，一般背包问题求解的是“在一定重量限制下，得到的最大价值是多少”。我们这里有些变化，是要求“总价值达到或超过K的前提下，成本（重量）最小是多少”。

不过我们仍然可以使用求解背包问题的DP思想，令f[x]表示建设值是x时，需要的最低成本是多少。

f[] = {INF}
f[0] = 0
for i = 1 .. M   //枚举物品
    B'[i] = B[i]/(T^(c-1))
    for x = B'[i] ..    //枚举价值
        f[x] = min(f[x], f[x-B'[i]] + A[i])
ans = INF
for x = K .. 
    ans = min(ans, f[x])

这里我们遇到了一个比较头疼的问题。建设值x的取值范围上限是多少？

我们要求的ans是f[K], f[K+1], ... 的最小值。我们可以知道当x超过K+max{B[i] | i=1..M}时，f[x]不会是最小的，但是f[B[i]]都有可能是我们要求的答案。举个极端的例子，如果某种重金属建设值是1000000000,而成本是1，其他重金属成本都是大于10正整数。那么f[1000000000]=1才是我们要求的答案。根据题意B[]的取值范围是32bit正整数，难道我们对x的枚举要达到2^31-1吗？这样显然会超时。

当然这个问题有时间复杂度更低的解决方案。假如某个f[x]是f[K], f[K+1], ... 中最小的，那么x的前驱状态y（也就是说f[x]是通过转移f[x] = f[y] + A[i]得到的)必然是小于等于K的。否则的话由于f[y]比f[x]更小，f[y]才应该是f[K], f[K+1], ... 中最小的。

所以我们可以略微改变一下转移的方式，用f[y]的值去更新f[x]的值。并且如果遇到x大于K，就把f[x]的值算在f[K]的头上。

f[] = {INF}
f[0] = 0
for i = 1 .. M   //枚举物品
    B'[i] = B[i]/(T^(c-1))
    for y = 0 .. K   //枚举价值
        x = y + B'[i]
        f[min(K, x)] = min(f[min(K, x)], f[y] + A[i])
ans = f[K]

本题大致思路如上，还有一些细节问题比如判断误解就不再赘述。总复杂度O(QNMK)。

对背包或完全背包不熟悉的同学可以先参考 01背包 和 完全背包。