current position:Home>C. Robot in a Hallway (recursion/prefix sum/dynamic programming)

C. Robot in a Hallway (recursion/prefix sum/dynamic programming)

2022-08-06 09:23:06Luo gkv

题目

题意

给定一个2*m的格子,要求从点(1,1)出发,And traverse the other grid,且每个格子只能走一次.每个格子(i,j)Has set lock timea[i][j],表示在时刻a[i][j]之前,Can't access the grid.

Ask according to the requirements,Traverse all the grid,And meet the above conditions under the condition of,最少需要多少时间.

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

思路

起点固定,是从(1,1)开始,But the finish is not fixed,We can set your own path.
可以分为两大类,The finish on the second line,And the finish in the first line of scene.

1.1The finish on the second line
此时,我们可以发现,The end can only be set in奇数列
在这里插入图片描述
1.2The finish in the first line
此时,我们可以发现,The end can only be set in偶数列
在这里插入图片描述

Total feasible route has a lot of,If violence computing enumeration,会TLE.
考虑优化.We have to end in the second example.
在这里插入图片描述
We will route,Split into red line+橙色路线.
The red line is snakeskin walk,The orange line isUGlyph walk a.

2.1The orange line recursive relations
观察上图中,Each scenario orange line relationship.我们发现,终点在a[2][i]The orange line the minimum spend time,Can end ina[2][i+2]The orange line the minimum spend time递推而来.
初始化:

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

递推关系式:

dp_end[i] = dp_end[i+2] + 2;// Because the end away from the2个单位,需要加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
// 下面的countRefers to the orange line grid Numbers.
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.2The recursion relation of red line
The recursion relation of red line is relatively more simple,直接模拟即可.

dp_start[1] = a[1][1];// 初始点
for (int i = 2; i <= m; ++i) {
    
	// The red line,走到第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.3Calculate the minimum time

Good computing red line and orange line,You can calculate the final result.
Red route from starting point to the red line end,需要的最小时间.
The orange line said from the orange line starting point,走到终点,需要的最小时间.
The cost of the current route time is
max(Red line need time+Walk to the end of time,The orange line)

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

其他注意事项

  • 要区分mFor the odd and even number of scene
  • Grid least time need locka[i][j],So it is in the firsta[i][j]+1Time to visit.
  • 注意取long long,The data overflow

经典的dp题,细节比较多,详见代码.

PS:Too sleepy last night didn't finish writing ran to go to bed,Drop points, it doesn't matter233

代码

#include <bits/stdc++.h>
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;// The current orange route node number 
    if (sub_flag) {
    // 如果终点,There's a list of,需要额外考虑 
    	--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]Said the finish in the firstiColumns of the orange line,的最小花费时间 
    for (int i = ed - 2; i >= st; i -= 2) {
    
    	count += 2;// 添加2元素 
    	dp_end[i] = dp_end[i+2] + 2;// Because the end away from the2个单位,需要加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 */

最后

Think of my article is good,weixin gongzhonghao搜 The other isdebug,关注下,Happy together brush problem~

copyright notice
author[Luo gkv],Please bring the original link to reprint, thank you.
https://en.chowdera.com/2022/218/202208060918144341.html

Random recommended