题意

市民需要从左岸（位置$0$）出发，经过若干柱子（位置$1$~$n$），到达右岸（位置$n + 1$）。每个柱子在时间$0$时降下，之后按周期$a[i]$（升起时间）和$b[i]$（降下时间）循环。移动规则为：每个时间单位可移动到当前位置左右$5$个柱子范围内的可用位置（包括河岸，柱子需处于升起状态）。目标是求到达右岸的最早时间。

解题思路

这是一个典型的 广度优先搜索（$BFS$） 问题，可转化为动态规划（$DP$）问题，按时间顺序维护可达位置。核心是状态转移：每个时间点的可达位置仅依赖于前一时间点的可达位置及其周围$5$个范围内的可用位置。

状态定义

位置：左岸（$0$）、柱子（$1$~$n$）、右岸（$n + 1$），共$n + 2$个位置。 时间：从$0$开始递增，使用滚动数组$dp[2][n + 2]$，其中$dp[tmp][pos]$表示时间$t$时能否到达$pos$（$tmp = 0$或$1$，交替表示当前时间和下一时刻）。

转移条件

河岸可用性：左岸（$0$）和右岸（$n + 1$）在任何时间都可用。 柱子可用性：柱子$i$在时间$t$可用，当且仅当$(a[i] + b[i]) \in [1, a[i]]$ （时间$0$时柱子降下，从时间$1$开始升起，持续$a[i]$时间，随后降下$b[i]$时间，循环）。 移动范围：从位置$pos$，下一时刻可移动到$[pos - 5, pos + 5]$范围内的有效位置（$0 \leq next\_pos \leq n + 1$），且目标位置在该时刻可用。

初始状态

时间$0$时，市民在左岸，故$dp[0][0] = 1$。

遍历过程

按时间$t$从$0$开始递增，每次计算下一时刻$t + 1$的可达位置： $1$.遍历当前时刻所有可达位置$pos$，对其周围$5$个范围内的每个位置$next\_pos$，检查是否可用。 $2$.若可用且未被访问过，标记$dp[1 - tmp][next\_pos] = 1$。 $3$.一旦右岸（$n + 1$）被标记为可达，立即返回当前时间$t + 1$。

标程

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#include <vector>
#include <stack>
#include <list>
#include <map>

using namespace std;

#define inf 0x3f3f3f3f
#define Max 110

int max(int a, int b) {
    return a > b ? a : b;
}

int min(int a, int b) {
    return a < b ? a : b;
}

int dp[2][1010], t, a[1010], b[1010];

int main() {
    int i, j, k, tmp, rec, n;
    std::scanf("%d", &t);
    while (t--) {
        std::scanf("%d", &n);
        for (i = 1; i <= n; i++) {
            std::scanf("%d%d", &a[i], &b[i]);
        }
        tmp = 0;
        std::memset(dp[tmp], 0, sizeof(dp[tmp]));
        dp[0][0] = 1;
        rec = inf;
        for (i = 0; i <= n; i++) {
            std::memset(dp[1 - tmp], 0, sizeof(dp[1 - tmp]));
            for (j = 0; j <= n + 1; j++) {
                if (j == 0 || j > n || (i % (a[j] + b[j]) >= 1 && i % (a[j] + b[j]) <= a[j])) {
                    for (k = j - 1; j - k <= 5 && k >= 0; k--) {
                        if (dp[tmp][k]) {
                            dp[1 - tmp][j] = 1;
                            break;
                        }
                    }
                    if (dp[1 - tmp][j]) continue;
                    for (k = j; k <= n + 1 && k - j <= 5; k++) {
                        if (dp[tmp][k]) {
                            dp[1 - tmp][j] = 1;
                            break;
                        }
                    }
                }
            }
            if (dp[1 - tmp][n + 1]) {
                rec = i;
                break;
            }
            tmp = 1 - tmp;
        }
        if (rec != inf) {
            std::cout << rec << std::endl;
        } else {
            std::cout << "NO" << std::endl;
        }
    }
    return 0;
}