第十七届同济大学程序设计预选赛暨高校网络友谊赛 C-张老师的旅行

链接：https://ac.nowcoder.com/acm/contest/5477/C
来源：牛客网

题目描述

张老师到了一个王国去旅游，王国有n个景点，张老师到达这个城市所在的车站恰好位于第x个景点，这个王国非常特别，恰好所有著名的景点都在分布在直线上，每个景点在坐标pi上(单位：公里)，张老师身体非常好，每走一公里花费一分钟。每个景点都有一个打卡点，并且必须在不迟于相应的时间（时间从张老师到达王国开始计算）前到达才能打卡成功并且给以一个打卡标记，集齐所这些标记就能获得一个大礼包。由于张老师非常想要大礼包，并且因为张老师还着急去下一个王国旅游，所以张老师希望用的时间尽量少，你能帮帮张老师吗？

输入描述:

输入的第一行，包含一个整数n（1≤n≤1000）。
第二行包含n个整数pi(1≤pi≤100000)，第i个整数pi为第i个景点的坐标（坐标从小到大排列）。
最后一行包含n个整数ti(0≤ti≤10,000,000)，ti表示第i个景点最迟到达的时间，时间为0则表示张老师所在车站的位置且只有一个为0。

输出描述:

输出所需的最少时间，若无解输出-1。

示例1

输入

[复制](javascript:void(0)😉

4
1 2 3 4
0 1 2 3

输出

[复制](javascript:void(0)😉

3

思路：

这是一个区间DP的问题，

设\(dp_R[i][j]\)代表打卡完了第\([i,j]\)所有景点后在最右端（第\(\mathit j\)个景点）时花费的最小时间。

设\(dp_L[i][j]\)代表打卡完了第\([i,j]\)所有景点后在最左端（第\(\mathit i\)个景点）时花费的最小时间。

初始状态：

\(pos\)=张老师最初所在车站的位置

\(dp_R[pos][pos]=dp_L[pos][pos]=0\)

状态转移：

\(dp_R[i][j]\)分别可以从\(dp_R[i][j-1],dp_L[i][j-1]\)两个状态转移过来。

\(dp_L[i][j]\)分别可以从\(dp_R[i+1][j],dp_L[i+1][j]\)两个状态转移过来。

转移是判断下最短耗时是否小于等于对应景点的限制时间。

代码：

const int maxn = 1010;
const int inf = 0x3f3f3f3f;
/*** TEMPLATE CODE * * STARTS HERE ***/
#define DEBUG_Switch 0
int n;
int p[maxn];
int dp_L[maxn][maxn];
int dp_R[maxn][maxn];
int t[maxn];
int main()
{
#if DEBUG_Switch
    freopen("C:\\code\\input.txt", "r", stdin);
#endif
    //freopen("C:\\code\\output.txt","r",stdin);
    n = readint();
    repd(i, 1, n)
    {
        p[i] = readint();
    }
    repd(i, 1, n) {
        repd(j, 1, n)
        {
            dp_R[i][j] = inf;
            dp_L[i][j] = inf;
        }
    }
    repd(i, 1, n)
    {
        t[i] = readint();
        if (t[i] == 0)
        {
            dp_L[i][i] = 0;
            dp_R[i][i] = 0;
        }
    }
    repd(len, 2, n)
    {
        for (int i = 1; i <= n - len + 1; ++i)
        {
            int j = i + len - 1;
            int temp;
            temp = dp_R[i][j - 1] + abs(p[j - 1] - p[j]);
            if (temp <= t[j])
            {
                dp_R[i][j] = min(temp, dp_R[i][j]);
            }
            temp = dp_L[i][j - 1] + abs(p[i] - p[j]);
            if (temp <= t[j])
            {
                dp_R[i][j] = min(temp, dp_R[i][j]);
            }
            temp = dp_R[i + 1][j] + abs(p[j] - p[i]);
            if (temp <= t[i])
            {
                dp_L[i][j] = min(temp, dp_L[i][j]);
            }
            temp = dp_L[i + 1][j] + abs(p[i + 1] - p[i]);
            if (temp <= t[i])
            {
                dp_L[i][j] = min(temp, dp_L[i][j]);
            }
        }
    }
    int ans = min(dp_R[1][n], dp_L[1][n]);
    if (ans == inf)
        ans = -1;
    printf("%d\n", ans );
    return 0;
}