题意分析

蜘蛛侠每天进行攀爬训练，每次训练由$M$个阶段组成，每个阶段需要攀爬$d_i$米。他可以选择向上或向下攀爬，但必须满足以下条件：

1. 训练开始和结束时处于地面$0$米处。
2. 训练过程中不能低于地面$0$米。
3. 建筑物的高度必须至少比训练期间到达的最高点高出$2$米。

我们需要找到一个合法的攀爬方案（用"U"和"D"表示），使得所需的建筑物高度最小。如果无解，输出"IMPOSSIBLE"。

解题思路

• 动态规划状态设计：设$dp[i][j]$表示前$i$个阶段结束时处于高度$j$时的最小最大高度。
• 状态转移：
  • 如果第$i$阶段选择向上攀爬，则$j$增加$a[i]$，且$j \geq 0$。
  • 如果第$i$阶段选择向下攀爬，则$j$减少$a[i]$，且$j \geq 0$。
  • 更新$dp[i][j]$为当前最大高度和之前状态的最大高度的较小值。
• 路径记录：使用$pre[i][j]$记录状态转移的前驱高度，以便回溯输出方案。

实现步骤

1. 初始化：将$dp$数组初始化为无穷大，$dp[0][0] = 0$。
2. 状态转移：
   • 遍历每个阶段$i$和可能的高度$j$。
   • 尝试向上或向下攀爬，更新$dp[i][j]$和$pre[i][j]$。
3. 结果判断：
   • 如果$dp[n][0]$仍为无穷大，输出"IMPOSSIBLE"。
   • 否则，回溯$pre$数组输出方案。

C++实现

#include <iostream>
#include <string.h>
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <stdlib.h>
 
using namespace std;
#define MAX 10000000
int dp[45][1005];
int pre[45][1005];
int n;
int a[45];
void dfs(int x,int height)
{
        if(x==0)
                return;
        dfs(x-1,pre[x][height]);
        if(height>pre[x][height])
                printf("U");
        else
                printf("D");
}
int main()
{
        int t;
        scanf("%d",&t);
        while(t--)
        {
                scanf("%d",&n);
                for(int i=1;i<=n;i++)
                {
                        scanf("%d",&a[i]);
                }
                for(int i=0;i<=n;i++)
                        for(int j=0;j<=1000;j++)
                                dp[i][j]=MAX;
                dp[0][0]=0;
                for(int i=1;i<=n;i++)
                {
                        for(int j=0;j<=1000;j++)
                        {
                                if(j-a[i]>=0&&dp[i-1][j-a[i]]!=MAX)
                                {
                                        if(dp[i][j]>max(dp[i-1][j-a[i]],j))
                                        {
                                            dp[i][j]=max(dp[i-1][j-a[i]],j);
                                           pre[i][j]=j-a[i];
                                        }                                                                                                                                                                                                              
                                }
                                if(j+a[i]<=1000&&dp[i-1][j+a[i]]!=MAX)
                                {
                                        if(dp[i][j]>max(dp[i-1][j+a[i]],j))
                                        {
                                                dp[i][j]=max(dp[i-1][j+a[i]],j);
                                                pre[i][j]=j+a[i];
                                        }
                                }
                        }
                }
                if(dp[n][0]==MAX)
                        printf("IMPOSSIBLE\n");
                else
                {
                        dfs(n,0);
                        printf("\n");
                }
        }
        return 0;
}

代码说明

• 全局变量：
  • $dp[i][j]$：动态规划数组，记录前$i$阶段高度$j$的最小最大高度。
  • $pre[i][j]$：记录状态转移的前驱高度。
  • $a[i]$：存储每个阶段的攀爬距离。
• 函数$dfs$：回溯输出方案，根据$pre$数组判断每一步是向上（"U"）还是向下（"D"）。
• 主函数：
  • 初始化$dp$数组为无穷大，$dp[0][0] = 0$。
  • 遍历每个阶段和高度，尝试向上或向下攀爬，更新$dp$和$pre$。
  • 判断是否有解，若无解输出"IMPOSSIBLE"，否则回溯输出方案。