张老师的旅行

题意

n个点在数轴上排列，从其中一个点出发。每个点都有要求的最晚到达时间，问能否全部准时到达，如果能，给出完成时间。

分析

题目给出的n个景点是按照位置信息升序排列的。

把起始点，即t为0的点设为k，所有的点分成了两部分：k点左边的点和k点右边的点。

我们用一个数组dp[i][j][f]表示完成左边i个点右边j个点的最少所需时间，f==0时表示在左边结束，f==1时表示在右边结束。

看着数轴，考虑在左边结束的情况，即dp[i][j][0]：

1. 上一个落脚点是左边（从右往左数，下同）第i-1个点，那么就是dp[i-1][j][0]再加上两点之间所需要消耗的时间即可。
2. 上一个落脚点是右边第j个点.

所以

同理

然后逐个比对，遇到不符合的情况直接退出即可。

solution

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 1e3 + 5;
int dp[N][N][2];
int d[N], t[N];
int main() {
    int n,k;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> d[i];
    for (int i = 1; i <= n; i++) cin >> t[i];
    for (int i = 1; i <= n; i++) if (t[i] == 0) k = i;
    fill(**dp, **dp+sizeof(dp)/4, INF);
    dp[0][0][1] = dp[0][0][0] = 0;
    for (int i = 0; i <= k - 1; i++) 
        for (int j = 0; j <= n - k; j++) {
            if (i) dp[i][j][0] = min(dp[i - 1][j][0] - d[k - i] + d[k - i + 1], dp[i - 1][j][1] + d[j + k] - d[k - i]);
            if (j) dp[i][j][1] = min(dp[i][j - 1][1] + d[j + k] - d[j - 1 + k], dp[i][j - 1][0] + d[j + k] - d[k - i]);
            if (dp[i][j][0] > t[k - i] && dp[i][j][1] > t[j + k]) { cout << -1; return 0; }
            if (dp[i][j][0] > t[k - i]) dp[i][j][0] = INF;
            if (dp[i][j][1] > t[k + j]) dp[i][j][1] = INF;
        }
    cout << min(dp[k - 1][n - k][0], dp[k - 1][n - k][1]);
    return 0;
}

因为这是我第一次写区间DP，所以翻了很多沙雕错误。

1. 区间DP的起始点是for (int i = 0; i <= x; i++)这样的。
2. 再比如这样的求最小，是把所有的不合法位置初始化为INF。
3. 还有就是一些非常沙雕的越界了。

题目思路我就花了十几分钟……