动态规划的优化方式 Day1 单调队列优化

#include <bits/stdc++.h>
#define N 500010
using namespace std;

int sum[N], a[N];
deque<int> q;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
  
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sum[i] = sum[i - 1] + a[i];
    }
    int ans = -INT_MAX;
    for (int i = 1; i <= n; i++) {
        while (!q.empty() && sum[i - 1] < sum[q.front()]) q.pop_front();
        q.push_front(i - 1);
        if (i - 1 - q.back() == m) q.pop_back();
        ans = max(ans, sum[i] - sum[q.back()]);
    }
    cout << ans << endl;
    return 0;
}

#include <bits/stdc++.h>
#define N 100010
using namespace std;

typedef long long ll;

ll dp[N];
ll sum;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> dp[i];
        sum += dp[i];
    }
    deque<ll> q;
    ll ans = INFINITY;
    q.push_front(0);
    for (int i = 1; i <= n; i++) {
        if (i - q.back() > k + 1) q.pop_back();
        dp[i] += dp[q.back()];
        while (!q.empty() && dp[i] < dp[q.front()]) q.pop_front();
        q.push_front(i);
    }
    for (int i = n - k; i <= n; i++) ans = min(ans, dp[i]);
    cout << sum - ans << endl;
    return 0;
}

#include <bits/stdc++.h>

#define N 1010
using namespace std;

int g[N][N];
int row_min[N][N], row_max[N][N], col_min[N], col_max[N];
int tmp[N];
int a, b, n;
deque<int> q;

void getMax(const int arr[], int dest[], int size) {
    // Get max segmental element from arr and copy the result to dest
    q.clear();
    for (int i = 1; i <= size; i++) {
        if (!q.empty() && i - q.back() >= n) q.pop_back();
        while (!q.empty() && arr[i] >= arr[q.front()]) q.pop_front();
        q.push_front(i);
        dest[i] = arr[q.back()];
    }
}

void getMin(const int arr[], int dest[], int size) {
    q.clear();
    for (int i = 1; i <= size; i++) {
        if (!q.empty() && i - q.back() >= n) q.pop_back();
        while (!q.empty() && arr[i] <= arr[q.front()]) q.pop_front();
        q.push_front(i);
        dest[i] = arr[q.back()];
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> a >> b >> n;
    for (int i = 1; i <= a; i++) {
        for (int j = 1; j <= b; j++) {
            cin >> g[i][j];
        }
    }
    for (int i = 1; i <= a; i++) {
        getMax(g[i], row_max[i], b);
        getMin(g[i], row_min[i], b);
    }
    int res = INFINITY;
    for (int i = n; i <= b; i++) {
        for (int j = 1; j <= a; j++) tmp[j] = row_max[j][i];
        getMax(tmp, col_max, a);

        for (int j = 1; j <= a; j++) tmp[j] = row_min[j][i];
        getMin(tmp, col_min, a);

        for (int j = n; j <= a; j++) res = min(res, col_max[j] - col_min[j]);
    }
    cout << res << endl;
    return 0;
}