C. Robot in a Hallway（递推/前缀和/动态规划）

题目

题意

给定一个2*m的格子，要求从点(1,1)出发，并遍历完其他格子，且每个格子只能走一次。每个格子(i，j)有设定锁定时间a[i][j]，表示在时刻a[i][j]之前，不能访问该格子。

问按要求，遍历完所有格子，且满足上述条件的情况下，最少需要多少时间。

1<=m<=200000
1<=a[i][[j]<=1000000000

思路

起点固定，是从(1,1)开始，但终点不固定，我们可以设定自己的路线。
可以分为两大类，终点在第二行，以及终点在第一行的场景。

1.1终点在第二行
此时，我们可以发现，终点只能设置在奇数列

1.2终点在第一行
此时，我们可以发现，终点只能设置在偶数列

总的可行路线有很多，如果暴力计算枚举，会TLE。
考虑优化。我们以终点在第二行为例。

我们将路线，拆分成红色路线+橙色路线。
其中红色路线是蛇皮走位，橙色路线是U字形走位。

2.1橙色路线的递归关系
观察上图中，各个场景的橙色路线相互关系。我们发现，终点在a[2][i]的橙色路线的最小花费时间，可以由终点在a[2][i+2]的橙色路线的最小花费时间递推而来。
初始化：

dp_end[ed] = max(a[2][ed], a[1][ed]+1);
1

递推关系式：

dp_end[i] = dp_end[i+2] + 2;// 由于终点远离了2个单位，需要加2
dp_end[i] = max(dp_end[i], a[2][i]);// 新增点 a[2][i]
dp_end[i] = max(dp_end[i], a[2][i+1] + 1);// 新增点 a[2][i+1] + 1
// 下面的count指上个橙色路线的格子数。
dp_end[i] = max(dp_end[i], a[1][i+1] + count);// 新增点 a[1][i+1]
dp_end[i] = max(dp_end[i], a[1][i] + count + 1);// 新增点 a[1][i]
1
2
3
4
5
6

2.2红色路线的递推关系
红色路线的递推关系相对就比较简单了，直接模拟即可。

dp_start[1] = a[1][1];// 初始点
for (int i = 2; i <= m; ++i) {
	// 计算红色路线，走到第i列，所需要的最少时间。
    dp_start[i] = dp_start[i-1];
    cur = 3 - cur;

    step = max(step + 1, a[cur][i-1]);// 向上/下 走一格
    dp_start[i] = max(dp_start[i], step);


    step = max(step + 1, a[cur][i]);// 向右 走一格
    dp_start[i] = max(dp_start[i], step);
}
1
2
3
4
5
6
7
8
9
10
11
12
13

2.3计算最小花费时间

计算好红色路线和橙色路线的时间，便可以计算最终结果了。
红色路线表示从起点走到红色路线终点，需要的最小时间。
橙色路线表示从橙色路线起点，走到终点，需要的最小时间。
当前路线的花费时间即为
max(红色路线需要的时间+走到终点的时间，橙色路线的时间)

ans = min(ans, max(dp_start[i] + (m - i) * 2 + 1, dp_end[i]));
1

其他注意事项

• 要区分m为奇数和偶数的场景
• 格子时间最少需要锁a[i][j]，因此它在第a[i][j]+1时刻才能访问。
• 注意取long long，防数据溢出

经典的dp题，细节比较多，详见代码。

PS：昨晚太困了没写完就跑去睡了，掉分也无所谓了233

代码

#include 
using namespace std;
#define ll long long
const int maxn = 200010;

int m;
ll a[3][maxn];
ll dp_start[maxn];
ll dp_end[maxn];

void cal_end(int ed, int st, bool sub_flag, int cur) {
	int count = 0;// 统计当前橙色路线的节点个数 
    if (sub_flag) {// 如果终点，后边还有一列，需要额外考虑 
    	--ed;
    	dp_end[ed] = a[cur][ed];
    	dp_end[ed] = max(dp_end[ed], a[cur][m] + 1);
    	dp_end[ed] = max(dp_end[ed], a[3-cur][m] + 2);
    	dp_end[ed] = max(dp_end[ed], a[3-cur][ed] + 3);
    	count += 4;
	} else {
		dp_end[ed] = a[cur][ed];
		dp_end[ed] = max(dp_end[ed], a[3-cur][ed] + 1);
		count += 2;
	}
	// dp_end[i]表示终点在第i列的橙色路线，的最小花费时间 
    for (int i = ed - 2; i >= st; i -= 2) {
    	count += 2;// 添加2元素 
    	dp_end[i] = dp_end[i+2] + 2;// 由于终点远离了2个单位，需要加2
    	dp_end[i] = max(dp_end[i], a[cur][i]);// 新增点 a[cur][i]
    	dp_end[i] = max(dp_end[i], a[cur][i+1] + 1);// 新增点 a[cur][i+1]
    	// 下面的 3-cur是取 上/下 一列 
    	dp_end[i] = max(dp_end[i], a[3-cur][i+1] + count);// 新增点 a[3-cur][i+1]
    	dp_end[i] = max(dp_end[i], a[3-cur][i] + count + 1);// 新增点 a[3-cur][i]
    	count += 2;// 添加2元素 
	}
}
void cal_start() {
	ll step = 0;
    int cur = 1;
    dp_start[1] = a[1][1];
    // dp_start[i] 表示 红色路线，走到第i列，所需要的最少时间。
    for (int i = 2; i <= m; ++i) {
        dp_start[i] = dp_start[i-1];
        cur = 3 - cur;

        step = max(step + 1, a[cur][i-1]);// 向上/下 走一格
        dp_start[i] = max(dp_start[i], step);


        step = max(step + 1, a[cur][i]);// 向右 走一格
        dp_start[i] = max(dp_start[i], step);
    }
}
void debug() {
	printf("a:\n");
    for (int i = 1; i <= 2; ++i) {
        for (int j = 1; j <= m; ++j) {
            printf("%lld ", a[i][j]);
        }
        printf("\n");
    }
    printf("dp_start:\n");
    for (int i = 1; i <= m; ++i) {
        printf("%lld ", dp_start[i]);
    }
    printf("\ndp_end:\n");
    for (int i = 1; i <= m; ++i) {
        printf("%lld ", dp_end[i]);
    }
    printf("\n");
}
void solve() {
    scanf("%d", &m);
    for (int i = 1; i <= 2; ++i) {
        for (int j = 1; j <= m; ++j) {
            scanf("%lld", &a[i][j]);
            if (a[i][j]) ++a[i][j];// 方便处理，非0值都加1 
        }
    }
    for (int i = 1; i <= m; ++i) {
        dp_start[i] = 0;
        dp_end[i] = 0;
    }
    cal_start();
	cal_end(m, 1, m % 2 == 0, 2);
    cal_end(m, 2, m & 1, 1);
    
    
//    debug();
    

    int cur = 1;
    ll ans = max(dp_start[1] + (m - 1) * 2 + 1, dp_end[1]);
    for (int i = 2; i <= m; ++i) {
        cur = 3 - cur;
        ans = min(ans, max(dp_start[i] + (m - i) * 2 + 1, dp_end[i]));
    }
    printf("%lld\n", ans);
}

int main() {
    int t;
//	t = 1;
    scanf("%d", &t);
    int cas = 1;
    while (t--) {
		solve();
    }
}
/*
99
2
0 1
0 0

 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116

最后

觉得我文章还不错的话，weixin gongzhonghao搜 对方正在debug，关注下，一起快乐刷题吧~