codeforces 762 D. Maximum path（dp）

题目链接：http://codeforces.com/problemset/problem/762/D

题意：给出一个3*n的矩阵然后问从左上角到右下角最大权值是多少，而且每一个点可以走上下左右，但是一个点

不能被经过两次及以上。

题解：一看感觉是一道插头dp但是，由于只是3 * n的矩阵，所以必定有规律。然而规律也挺好找的。只要往回走必定会取完3行。

而且走法都有规律的最好自行画图理解一下。

#include <iostream>

#include <cstring>

#define inf 1000000000000000

using namespace std;

const int M = 1e5 + 10;

long long a[4][M];

long long dp[M][4];

long long sum(int pos , int l , int r) {

    if(l > r) {

        swap(l , r);

    }

    long long sum = 0;

    for(int i = l ; i <= r ; i++) {

        sum += a[i][pos];

    }

    return sum;

}

int main() {

    int n;

    cin >> n;

    for(int i = 0 ; i < 3 ; i++) {

        for(int j = 1 ; j <= n ; j++) {

            cin >> a[i][j];

        }

    }

    for(int i = 0 ; i <= n ; i++) {

        for(int j = 0 ; j <= 3 ; j++) {

            dp[i][j] = -inf;

        }

    }

    dp[0][0] = 0;

    for(int i = 1 ; i <= n ; i++) {

        for(int j = 0 ; j < 3 ; j++) {

            for(int k = 0 ; k < 3 ; k++) {

                dp[i][j] = max(dp[i][j] , dp[i - 1][k] + sum(i , j , k));

            }

        }

        dp[i][0] = max(dp[i][0] , dp[i - 1][3] + sum(i , 0 , 2));

        dp[i][2] = max(dp[i][2] , dp[i - 1][3] + sum(i , 0 , 2));

        dp[i][3] = max(dp[i][3] , max(dp[i - 1][0] , dp[i - 1][2]) + sum(i , 0 , 2));

    }

    cout << dp[n][2] << endl;

    return 0;

}

巴特西

codeforces 762 D. Maximum path（dp）

最新文章

热门文章