# 「RdOI R35 附加」ACP-II## 题目背景在 1951 年第 -32 届全国青少年信息学奥林匹克冬令营结束后打了一上午比赛的小 A 疲惫不堪想放松一下。于是他又借助时空传输接口Time Transport Interface连接了一台 2015 年的计算机获取到了最新的游戏「AC Project 15 Legacy of DWT AKing IOI」来游玩。## 题目描述这是一道传

解题思路

这是一道模拟题，需要按照题目描述的规则进行模拟。

首先，我们可以先思考如何判断机器人是否会在第 $d$ 秒内碰撞到子弹或者移动到画面以外。对于每一秒的判定阶段，我们可以遍历所有已经生成但还未销毁的子弹，计算子弹在这一秒初和这一秒末的位置，然后判断机器人的当前坐标是否在这条线段上。

接下来，我们需要确定机器人的移动指令。我们可以通过枚举所有的指令排列组合，计算每个指令序列的费用，并判断是否能够成功完成游戏。具体来说，我们可以使用一个递归函数来生成所有的指令序列，递归的参数包括当前指令序列的长度和费用。在递归函数中，我们枚举下一个指令的类型，计算当前指令的费用并加到总费用上，然后递归调用下一层。如果当前指令序列的长度等于 $k$，说明已经生成了 $k$ 遍指令序列，我们就可以判断这个指令序列是否能够成功完成游戏。

在递归函数中，我们还需要记录机器人的位置，以便在判定阶段进行碰撞判断。我们可以使用两个变量 x 和 y 来记录机器人的横纵坐标。

当我们枚举完所有的指令序列后，我们就可以得到所有可以成功完成游戏的指令序列的费用。然后根据题目要求，输出最小费用的指令序列的费用或者构造一组指令序列。

算法步骤

1. 读入输入数据，包括 $n,m,b,d,k$ 和指令的费用 $P_i$。
2. 枚举所有的指令序列，计算每个指令序列的费用，并判断是否能够成功完成游戏。
3. 根据题目要求，输出最小费用的指令序列的费用或者构造一组指令序列。

代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n, m, b, d, k;
vector<int> P;
vector<vector<int>> bullets;
vector<int> instructions;
int minCost = INT_MAX;

// 判断机器人是否碰撞到子弹或者移动到画面以外
bool isCollide(int x, int y, int l, int r, int xi, int yi, int pi, int qi) {
    // 计算子弹在这一秒初和这一秒末的位置
    int x1 = xi + (l - xi) * pi;
    int y1 = yi + (l - xi) * qi;
    int x2 = xi + (r - xi) * pi;
    int y2 = yi + (r - xi) * qi;

    // 判断机器人的当前坐标是否在子弹的路径上（包括端点）
    if ((x >= x1 && x <= x2 && y >= y1 && y <= y2) ||
        (x >= x2 && x <= x1 && y >= y2 && y <= y1)) {
        return true;
    }
    return false;
}

// 递归生成所有的指令序列
void generateInstructions(int len, in