DP+單調隊列優化 E One hundred layer
題意:n*m的矩形,從第一層x位置往下走,每一層都可以往左或往右移動最多k步再往下走,問走到n層時所走路徑的最大值.
分析:定義
, ,注意到max裡的東西與j無關,可以定義單調隊列維護 的最值,注意t的限制條件.往右的情況類似.#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;
}
編譯人生,運作世界!