2012 Multi-University #8

DP+单调队列优化 E One hundred layer

题意：ｎ＊ｍ的矩形，从第一层ｘ位置往下走，每一层都可以往左或往右移动最多ｋ步再往下走，问走到ｎ层时所走路径的最大值．

分析：定义,,注意到max里的东西与ｊ无关，可以定义单调队列维护的最值，注意ｔ的约束条件．往右的情况类似．

#include <bits/stdc++.h>

const int N = 1e2 + 5;

const int M = 1e4 + 5;

const int INF = 0x3f3f3f3f;

int dp[N][M];

int a[N][M];

int sum[M];

int n, m, x, t;

struct Node {

    int v, id;

};

int main() {

    while (scanf ("%d%d%d%d", &n, &m, &x, &t) == 4) {

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

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

                scanf ("%d", &a[i][j]);

            }

        }

        std::deque<Node> dque;

        memset (dp, -INF, sizeof (dp));

        dp[1][x] = a[1][x];

        for (int i=x-1; i>=1 && i>=x-t; --i) {

            dp[1][i] = dp[1][i+1] + a[1][i];

        }

        for (int i=x+1; i<=m && i<=x+t; ++i) {

            dp[1][i] = dp[1][i-1] + a[1][i];

        }

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

            sum[0] = 0;

            dque.clear ();

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

                sum[j] = sum[j-1] + a[i][j];

                while (!dque.empty () && dque.front ().id < j - t) {

                    dque.pop_front ();

                }

                int tv = dp[i-1][j] - sum[j-1];

                while (!dque.empty () && dque.back ().v < tv) {

                    dque.pop_back ();

                }

                dque.push_back ((Node) {tv, j});

                dp[i][j] = dque.front ().v + sum[j];

            }

            sum[m+1] = 0;

            dque.clear ();

            for (int j=m; j>=1; --j) {

                sum[j] = sum[j+1] + a[i][j];

                while (!dque.empty () && dque.front ().id > j + t) {

                    dque.pop_front ();

                }

                int tv = dp[i-1][j] - sum[j+1];

                while (!dque.empty () && dque.back ().v < tv) {

                    dque.pop_back ();

                }

                dque.push_back ((Node) {tv, j});

                dp[i][j] = std::max (dp[i][j], dque.front ().v + sum[j]);

            }

        }

        int ans = dp[n][1];

        for (int i=2; i<=m; ++i) {

            ans = std::max (ans, dp[n][i]);

        }

        printf ("%d\n", ans);

    }

    return 0;

}