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

　　

?