题目
题意给定一个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);
递推关系式：
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]
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); }
2.3计算最小花费时间
计算好红色路线和橙色路线的时间，便可以计算最终结果了。 红色路线表示从起点走到红色路线终点，需要的最小时间。 橙色路线表示从橙色路线起点，走到终点，需要的最小时间。 当前路线的花费时间即为 max(红色路线需要的时间+走到终点的时间，橙色路线的时间)
ans = min(ans, max(dp_start[i] + (m - i) * 2 + 1, dp_end[i]));
其他注意事项
- 要区分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
*/
最后
觉得我文章还不错的话，weixin gongzhonghao搜 对方正在debug，关注下，一起快乐刷题吧~
