为csp认证做准备，现在开始尝试历年的4和5题的得分解法

第36次认证：跳房子
首先我直接打暴力：

#include <iostream>
#include <cstring>
using namespace std;

const int N = 100010;
int f[N];            //f[i]表示以i为结尾的最小步数
int a[N];
int k[N];
int n;

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++) scanf("%d", &a[i]);
    for (int i = 0; i < n; i ++) scanf("%d", &k[i]);
    memset(f, 0x3f, sizeof f);
    f[0] = 0;
    for (int i = 0; i < n; i ++)
        for (int j = 1; j <= k[i] && i + j < n; j ++)
            if (a[i + j] < j)
                f[i + j - a[i + j]] = min(f[i + j - a[i + j]], f[i] + 1);
    if (f[n - 1] == 0x3f3f3f3f) printf("-1\n");
    else printf("%d\n", f[n - 1]);
    return 0;
}

优化方法
这道题其实不难想到bfs

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

const int N = 100010;
int a[N], k[N];
int n;
int dist[N];

int bfs()
{
    if (n == 1) return 0;
    memset(dist, 0x3f, sizeof dist);
    dist[0] = 0;
    queue<int> q;
    q.push(0);
    while (q.size())
    {
        int t = q.front();
        q.pop();
        for (int i = 1; i <= k[t] && i <= n - 1 - t; i ++)
        {
            int u = t + i - a[t + i];
            if (dist[u] > dist[t] + 1)
            {
                dist[u] = dist[t] + 1;
                if (u == n - 1) return dist[u];
                q.push(u);
            }

        }
    }
    return -1;
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++) scanf("%d", &a[i]);
    for (int i = 0; i < n; i ++) scanf("%d", &k[i]);
    printf("%d\n", bfs());
    return 0;
}