问题描述

蜘蛛侠每天进行攀爬训练，训练由一系列高度序列描述。每次训练中，他可以选择向上爬或向下爬给定的高度，但必须满足以下条件：

训练开始和结束时必须在地面（高度为$0$）。

$1、$训练过程中任何时候都不能低于地面。

$2、$必须按照给定的高度顺序进行训练，不能重新排序。

$3、$训练过程中达到的最高高度要尽可能小，因为建筑物高度需要至少比最高点高2米。

方法思路

为了找到满足条件的最优路径，可以采用动态规划（$DP$）的方法。具体步骤如下：

$1、$状态定义：使用动态数组$dp[i][h]$表示处理到第$i$个步骤时，当前高度为h时的最小最大高度和对应的路径。

$2、$状态转移：对于每个步骤，考虑向上或向下移动：

向上移动：当前高度增加，更新最大高度。

向下移动：当前高度减少，确保不低于地面，不更新最大高度。

$3、$路径记录：在状态转移过程中，记录路径的选择（$"U"$或$"D"$）。

4、结果提取：处理完所有步骤后，检查是否存在结束高度为$0$的路径，并选择其中最大高度最小的路径。

#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <string>
#include <climits>
using namespace std;

struct State {
    int current_max_h;
    int sum_U;
    int pos;
    int step;
    string path;

    State(int h, int u, int p, int s, string pa)
        : current_max_h(h), sum_U(u), pos(p), step(s), path(pa) {}

    bool operator<(const State& other) const {
        if (current_max_h != other.current_max_h) {
            return current_max_h > other.current_max_h;
        }
        if (sum_U != other.sum_U) {
            return sum_U > other.sum_U;
        }
        return step > other.step;
    }
};

string solve(vector<int>& d, int M) {
    int sum_total = 0;
    for (int i = 0; i < d.size(); ++i) {
        sum_total += d[i];
    }
    if (sum_total % 2 != 0) {
        return "IMPOSSIBLE";
    }
    int target = sum_total / 2;

    priority_queue<State> pq;
    pq.push(State(0, 0, 0, 0, ""));

    // Replace unordered_map with map for C++98 compatibility
    vector<map<int, map<int, int> > > visited(M + 1);

    while (!pq.empty()) {
        State current = pq.top();
        pq.pop();

        if (current.step == M) {
            if (current.pos == 0 && current.sum_U == target) {
                return current.path;
            }
            continue;
        }

        if (visited[current.step][current.sum_U].find(current.pos) != visited[current.step][current.sum_U].end() &&
            visited[current.step][current.sum_U][current.pos] <= current.current_max_h) {
            continue;
        }
        visited[current.step][current.sum_U][current.pos] = current.current_max_h;

        int step = current.step;
        int current_d = d[step];

        // Try U
        int new_sum_U = current.sum_U + current_d;
        int new_pos = current.pos + current_d;
        int new_max_h = max(current.current_max_h, new_pos);
        if (new_pos >= 0 && new_sum_U <= target) {
            if (visited[step + 1][new_sum_U].find(new_pos) == visited[step + 1][new_sum_U].end() ||
                visited[step + 1][new_sum_U][new_pos] > new_max_h) {
                visited[step + 1][new_sum_U][new_pos] = new_max_h;
                pq.push(State(new_max_h, new_sum_U, new_pos, step + 1, current.path + "U"));
            }
        }

        // Try D
        new_sum_U = current.sum_U;
        new_pos = current.pos - current_d;
        new_max_h = max(current.current_max_h, current.pos);
        if (new_pos >= 0) {
            if (visited[step + 1][new_sum_U].find(new_pos) == visited[step + 1][new_sum_U].end() ||
                visited[step + 1][new_sum_U][new_pos] > new_max_h) {
                visited[step + 1][new_sum_U][new_pos] = new_max_h;
                pq.push(State(new_max_h, new_sum_U, new_pos, step + 1, current.path + "D"));
            }
        }
    }

    return "IMPOSSIBLE";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int N;
    cin >> N;
    while (N--) {
        int M;
        cin >> M;
        vector<int> d(M);
        for (int i = 0; i < M; ++i) {
            cin >> d[i];
        }
        cout << solve(d, M) << '\n';
    }

    return 0;
}