题意分析

本题是一个回合制策略游戏问题，英雄需要通过合理使用三种法术（闪电术、传送术、治疗术）击败怪物。关键在于理解每个法术的效果、怪物的移动规则以及战斗胜负的判定条件： 战斗机制： 英雄和怪物轮流行动，英雄先手 英雄每次行动必须消耗 1 点魔法值释放一个法术 怪物行动时向英雄移动，并在特定条件下攻击英雄 法术效果： 闪电术：对怪物造成与位置相关的伤害 传送术：重新定位怪物位置，可策略性调整战斗节奏 治疗术：恢复英雄生命值，提高生存能力 胜负条件： 英雄胜利：怪物总生命值 ≤ 0 英雄失败：魔法值耗尽且怪物未被击败，或生命值 ≤ 0

解答思路

本题可通过广度优先搜索（BFS）来寻找最优策略，核心在于：

状态定义：

英雄状态：生命值、魔法值 怪物状态：总生命值、当前位置 路径记录：已执行的法术序列

状态转移：

英雄回合：尝试三种法术，生成新状态 怪物回合：根据新位置移动并可能攻击英雄

剪枝优化：

使用哈希集合记录已访问状态，避免重复计算 优先处理步数少的状态，确保找到最短路径解

策略选择：

优先使用高伤害的闪电术 适时使用治疗术维持生存 合理使用传送术调整怪物位置，最大化伤害或规避攻击

代码

#include <vector>
#include <queue>
#include <string>
#include <cmath>
#include <tr1/unordered_set>  // 使用tr1命名空间兼容旧编译器
using namespace std;
using namespace std::tr1;     // 引入tr1命名空间

struct State {
    int hpHero;
    int mpHero;
    int hpMonsters;
    int posMonsters;
    string path;
    
    State(int h, int m, int hp, int p, string s) : 
        hpHero(h), mpHero(m), hpMonsters(hp), posMonsters(p), path(s) {}
    
    // 替换to_string为自定义整数转字符串函数
    string intToString(int num) const {
        if (num == 0) return "0";
        string result = "";
        bool isNegative = false;
        if (num < 0) {
            isNegative = true;
            num = -num;
        }
        while (num > 0) {
            result = (char)(num % 10 + '0') + result;
            num /= 10;
        }
        if (isNegative) result = "-" + result;
        return result;
    }
    
    string hash() const {
        return intToString(hpHero) + "," + intToString(mpHero) + "," + 
               intToString(hpMonsters) + "," + intToString(posMonsters);
    }
};

int main() {
    int N, HPH, MPH, HPM, NM, V, dH;
    cin >> N >> HPH >> MPH >> HPM >> NM >> V >> dH;
    
    vector<int> L(N + 1);
    for (int i = 1; i <= N; ++i) {
        cin >> L[i];
    }
    
    int initialHpMonsters = NM * HPM;
    
    queue<State> q;
    unordered_set<string> visited;
    
    State initial(HPH, MPH, initialHpMonsters, N, "");
    q.push(initial);
    visited.insert(initial.hash());
    
    bool found = false;
    State result(0, 0, 0, 0, "");
    
    while (!q.empty()) {
        State current = q.front();
        q.pop();
        
        // 检查怪物是否已被击败
        if (current.hpMonsters <= 0) {
            found = true;
            result = current;
            break;
        }
        
        // 英雄回合：尝试所有可能的法术
        // 1. 闪电术
        if (current.mpHero > 0) {
            int newHpMonsters = current.hpMonsters - L[current.posMonsters];
            if (newHpMonsters <= 0) {
                found = true;
                result = State(current.hpHero, current.mpHero - 1, newHpMonsters, 
                              current.posMonsters, current.path + "L\n");
                break;
            }
            
            // 计算怪物移动后的位置
            int newPosMonsters = max(1, current.posMonsters - V);
            int newHpHero = current.hpHero;
            if (newPosMonsters == 1) {
                int K = (newHpMonsters + HPM - 1) / HPM; // 天花板函数
                newHpHero -= K;
                if (newHpHero <= 0) continue;
            }
            
            State next(newHpHero, current.mpHero - 1, newHpMonsters, newPosMonsters, 
                      current.path + "L\n");
            string nextHash = next.hash();
            if (visited.find(nextHash) == visited.end()) {
                visited.insert(nextHash);
                q.push(next);
            }
        }
        
        // 2. 治疗术
        if (current.mpHero > 0 && current.hpHero < HPH) {
            int newHpHero = min(HPH, current.hpHero + dH);
            
            // 计算怪物移动后的位置
            int newPosMonsters = max(1, current.posMonsters - V);
            if (newPosMonsters == 1) {
                int K = (current.hpMonsters + HPM - 1) / HPM; // 天花板函数
                newHpHero -= K;
                if (newHpHero <= 0) continue;
            }
            
            State next(newHpHero, current.mpHero - 1, current.hpMonsters, newPosMonsters, 
                      current.path + "H\n");
            string nextHash = next.hash();
            if (visited.find(nextHash) == visited.end()) {
                visited.insert(nextHash);
                q.push(next);
            }
        }
        
        // 3. 传送术
        if (current.mpHero > 0) {
            for (int p = 1; p <= N; ++p) {
                // 计算怪物移动后的位置
                int newPosMonsters = max(1, p - V);
                int newHpHero = current.hpHero;
                if (newPosMonsters == 1) {
                    int K = (current.hpMonsters + HPM - 1) / HPM; // 天花板函数
                    newHpHero -= K;
                    if (newHpHero <= 0) continue;
                }
                
                State next(newHpHero, current.mpHero - 1, current.hpMonsters, newPosMonsters, 
                          current.path + "T " + State(0,0,0,0,"").intToString(p) + "\n");
                string nextHash = next.hash();
                if (visited.find(nextHash) == visited.end()) {
                    visited.insert(nextHash);
                    q.push(next);
                }
            }
        }
    }
    
    if (found) {
        cout << "VICTORIOUS" << endl;
        cout << result.path;
    } else {
        cout << "DEFEATED" << endl;
    }
    
    return 0;
}