?

?

DP+單調(diào)隊(duì)列優(yōu)化 E?One hundred layer

題意：ｎ＊ｍ的矩形，從第一層ｘ位置往下走，每一層都可以往左或往右移動(dòng)最多ｋ步再往下走，問走到ｎ層時(shí)所走路徑的最大值．

分析：定義,,注意到max里的東西與ｊ無(wú)關(guān)，可以定義單調(diào)隊(duì)列維護(hù)的最值，注意ｔ的約束條件．往右的情況類似．

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

　　

?

轉(zhuǎn)載于:https://www.cnblogs.com/Running-Time/p/5497935.html

總結(jié)

以上是生活随笔為你收集整理的2012 Multi-University #8的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。