求助c语言算法大神，不解决我睡不着啊！！！

2025-03-27 16:03:42

推荐回答（2个）

回答1：

动态规划args[a][b][c]的值
理解为走到a的位置、受到b个绿塔攻击、受到c个蓝塔减速时当前状态的最大伤害。
转移函数应该很好想把，就是把args[a-1][b][c],args[a-1][b-1][c],args[a-1][b][c-1]转移一遍，
也可以把a考虑成红塔个数。

回答2：

虽然一开始就想到动态规划，不知道为什么又想歪了>_<|||

下面的C++代码是按照@826010478 的提示写的。

#include 
#include 
#include 
#include 
#include 

struct Data {
    unsigned pos, Green, Blue;
};

inline bool operator<(Data const& a, Data const& b) {
    return std::memcmp(&a, &b, sizeof(Data)) < 0;
}
typedef unsigned long long damage_type;
typedef std::map Table;

struct goo {
    goo(damage_type const _x, damage_type const _y, damage_type const _z, damage_type const _t) :
        x(_x), y(_y), z(_z), t(_t) {}
    damage_type operator()(unsigned const n) {
        damage_type damage = 0;
        for (unsigned Green = 0; Green <= n; ++Green) {
            for (unsigned Blue = 0, MaxBlue = n - Green; Blue <= MaxBlue; ++Blue) {
                Data const key = { n, Green, Blue };
                damage = std::max(damage, Get(key));
            }
        }
        return damage;
    }
private:
    Table data;
    damage_type x, y, z, t;

    damage_type Get(Data const& key) {
        assert(key.pos >= key.Green + key.Blue);
        Table::iterator const it = data.find(key);
        if (it == data.end()) {
            damage_type damage = 0;
            if (key.pos > key.Green + key.Blue) {
                Data const tmp = { key.pos - 1,key.Green, key.Blue };
                damage = std::max(Get(tmp) + (key.Green * y + x) * (key.Blue * z + t), damage);
            }
            if (key.Green > 0) {
                Data const tmp = { key.pos - 1,key.Green - 1,  key.Blue };
                damage = std::max(Get(tmp) + (key.Green - 1) * y * (key.Blue * z + t), damage);
            }
            if (key.Blue > 0) {
                Data const tmp = { key.pos - 1, key.Green, key.Blue - 1 };
                damage = std::max(Get(tmp) + key.Green * y * ((key.Blue - 1) * z + t), damage);
            }
            data.insert(it, std::make_pair(key, damage));
            return damage;
        }
        else {
            return it->second;
        }
    }
};

int main() {
    unsigned n, x, y, z, t;

    std::cin >> n >> x >> y >> z >> t;

    std::cout << goo(x, y, z, t)(n) << "\n";

    return 0;
}

示例

另外，上面的代码用的是带备忘的自顶向下的方法，可以自行改为自底向上的算法。如果编译器支持，可以使用std::unordered_map（hash表）。

因为涉及的子问题的个数只有大概Binomial(n, 3)个，所以复杂度是O(n^3)。