CF762D Maximum path 题解

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

因此可以证明只能在第二排走回头路，且最多连续走一步。那么定义

dp_{i,j}

表示走到第

i

排第

j

列的最大价值，那么显然转移到

dp_{2,j}

时不能走回头路，转移到

dp_{1,j}

或

dp_{3,j}

时可以，只要在普通的动态规划上加上回头路即可。总时间复杂度量级为

O(n)

。

CPP

#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;
}

CF762D Maximum path 题解

文章操作

相关推荐

评论

CF762D Maximum path 题解