CF762D Maximum path 题解

_Jocularly_ · 2025-11-17 17:33:37 · 题解

首先观察题目，可知我们只能在第二排走回头路，因为如果在第一排或者第三排走的话，就永远也走不到终点，这一点显然可证。那么继续证明如果在第二排的话，最多只能连续走一步回头路。如下图显示，当走了奇数步回头路时，可以转化为第二张图所示的情况，二者代价和起终点等价，此时不需要走回头路；当走了偶数步回头路时，可以转化为第一张图所示的情况，二者代价和起终点等价，此时需要走一步回头路。

因此可以证明只能在第二排走回头路，且最多连续走一步。那么定义 dp_{i,j} 表示走到第 i 排第 j 列的最大价值，那么显然转移到 dp_{2,j} 时不能走回头路，转移到 dp_{1,j} 或 dp_{3,j} 时可以，只要在普通的动态规划上加上回头路即可。总时间复杂度量级为 O(n)。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
int a[5][100005];
int dp[5][100005];
signed main(){
    memset(dp,-0x3f,sizeof(dp));
    cin >> n;
    for(int i=1;i<=3;i++){
        for(int j=1;j<=n;j++){
            cin >> a[i][j];
        }
    }
    dp[1][0] = 0;
    for(int i=1;i<=n;i++){
        dp[2][i] = max({dp[1][i - 1] + a[1][i],dp[2][i - 1],dp[3][i - 1] + a[3][i]}) + a[2][i];
        dp[1][i] = max({dp[1][i - 1],dp[2][i - 1] + a[2][i],dp[3][i - 1] + a[3][i] + a[2][i]}) + a[1][i];
        if(i > 1) dp[1][i] = max(dp[1][i],dp[3][i - 2] + a[1][i] + a[1][i - 1] + a[2][i] + a[2][i - 1] + a[3][i] + a[3][i - 1]);
        dp[3][i] = max({dp[3][i - 1],dp[2][i - 1] + a[2][i],dp[1][i - 1] + a[1][i] + a[2][i]}) + a[3][i];
        if(i > 1) dp[3][i] = max(dp[3][i],dp[1][i - 2] + a[1][i] + a[1][i - 1] + a[2][i] + a[2][i - 1] + a[3][i] + a[3][i - 1]);
    }
    cout << dp[3][n];
    return 0;
}