C、张老师的旅行

区间dp，动态规划众多模型中的一种，解决区间问题上有广泛的应用。
基本思想就是一重循环枚举长度，还要一重循环枚举起点，终点就已经确定。
关于决策点根据题目是否需要枚举或者优化成记录这里不展开。本题不需要枚举决策点，因为老师需要花费时间最短一定是从区间这一边一直走到另一边。

那么我们根据题目意思找到n小于等于1000，可以开下2维的数组，我们就通过区间dp去解题。
使用一个三维数组，前两维表示左端点和右端点最后一个表示最后落点，0代表左端点，1代表右端点。它的值记录最短花费时间。
那么我们可以发现状态转移分别是：

• 从左端点继续向左
• 从右端点继续向右
• 从左端点一路向右到右端点后一个位置
• 从右端点一路向左到左端点前一个位置

当然这些状态转移的前提都是前一个位置的最小耗费，加上你的路途花费小于等于题目给定的t[i]。

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;

inline int read() {
    int s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}

const int N = 1e3 + 7; //节点
int dp[N][N][2];
int a[N], t[N];

int main() {
    int n = read();
    for (int i = 1; i <= n; ++i)    a[i] = read();
    int st = -1;
    for (int i = 1; i <= n; ++i) {
        t[i] = read();
        if (!t[i])    st = i;
    }
    memset(dp, 0x3f, sizeof(dp));
    dp[st][st][0] = dp[st][st][1] = 0;
    for (int len = 1; len <= n; ++len) { //长度
        for (int i = max(1, st - len + 1); i <= st && i + len - 1 <= n; ++i) { //起点
            int j = i + len - 1; //终点
            if (dp[i + 1][j][0] + a[i + 1] - a[i] <= t[i])
                dp[i][j][0] = min(dp[i][j][0], dp[i + 1][j][0] + a[i + 1] - a[i]);
            if (dp[i + 1][j][1] + a[j] - a[i] <= t[i])
                dp[i][j][0] = min(dp[i][j][0], dp[i + 1][j][1] + a[j] - a[i]);
            if (dp[i][j - 1][1] + a[j] - a[j - 1] <= t[j])
                dp[i][j][1] = min(dp[i][j][1], dp[i][j - 1][1] + a[j] - a[j - 1]);
            if (dp[i][j - 1][0] + a[j] - a[i] <= t[j])
                dp[i][j][1] = min(dp[i][j][1], dp[i][j - 1][0] + a[j] - a[i]);
        }
    }
    int ans = min(dp[1][n][0], dp[1][n][1]);
    if (ans == 0x3f3f3f3f)    puts("-1");
    else    printf("%d\n", ans);
    return 0;
}