Educational Codeforces Round 133 (Rated for Div. 2) C补题

比赛里不会做，感觉两个题都是dp qwq 然后果断放弃去睡大觉。

C题题目链接：

https://codeforces.com/contest/1716/problem/C

定义b[i][j]，为从(i,j)出发直走到下面/上面一个格子的需要的时间。

(注意不是途中用了多少时间，而是到达目标点的时间)

转移：

for (int i = 0; i < 2; i++) {
    for (int j = n - 1; j >= 0; j--) {
        b[i][j] = max({
            a[i ^ 1][j] + 1,
            a[i][j] + 1 + 2 * (n - j) - 1,
            b[i][j + 1] + 1 });
    }
}

最终代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
const int N=2e5+10;
int t,n;
int a[2][N],b[2][N];
void solve()
{
    cin >> n;
    for(int i = 0; i < 2; i++)for(int j = 0; j < n; j++) cin >> a[i][j];
    a[0][0] = -1;//为了防止后面+1，所以a[0][0] = - 1
    b[0][n] = b[1][n] = 0;
    for (int i = 0; i < 2; i++)
    {
        for (int j = n - 1; j >= 0; j--)
        {
            b[i][j] = max(
            {
                a[i ^ 1][j] + 1,
                a[i][j] + 1 + 2 * (n - j) - 1,
                b[i][j + 1] + 1 });
        }
    }
    int ans =INT_MAX;
    int cur = 0;
    for (int j = 0; j < n; j++)
    {
        int k = j & 1;
        ans = min(ans, max(cur  + 2 * (n - j)  - 1, b[k][j]));
        cur = max(cur, a[k][j] + 1);
        cur++;//模拟
        cur = max(cur, a[k ^ 1][j] + 1);
        cur++;//模拟
    }
    cout << ans << endl;
}
signed main()
{
    cin>>t;
    while(t--)
    {
        solve();
    }
    return 0;
}