单调队列优化dp

题意

伯纳德喜欢去看鲁道夫，但他总是迟到。问题是伯纳德需要乘坐渡船过河。鲁道夫决定帮助他的朋友解决这个问题。

河流是一个 $n$ 行 $m$ 列的网格。第 $i$ 行和第 $j$ 列的交点包含对应单元格的深度 $a_{i,j}$。所有的 第一列 和 最后一列 的单元格对应河岸，所以它们的深度为 0。

鲁道夫可以选择某一行 $(i,1), (i,2), \ldots, (i,m)$ 来建造一座桥梁。在这一行的每个单元格上，他可以安装一个桥梁支撑。安装支撑的成本为该单元格的深度加1，即 $a_{i,j}+1$。支撑必须安装满足以下条件：

1. 必须在单元格 $(i,1)$ 安装支撑；
2. 必须在单元格 $(i,m)$ 安装支撑；
3. 任意相邻支撑之间的距离必须 不超过 $d$。支撑之间的距离定义为 $|j_1 - j_2| - 1$，其中 $(i, j_1)$ 和 $(i, j_2)$ 是两个支撑。

建造一座桥梁很无聊。因此，鲁道夫决定在 连续的 k 行 上建造桥梁，即选择某些行 $i$ （$1 \leq i \leq n - k + 1$），并独立地在第 $i$ 行到第 $i + k - 1$ 行上建造桥梁。帮助鲁道夫 最小化 安装支撑的总成本。

思路

很明显的dp问题，设dp[i]为在截至到i号位置，且i号位置建造支撑的最小花费，需要从[i-d-1,i-1]的位置这个区间中挑一个最优的位置转移过来，这里直接用单调队列维护合法区间内成本最小的位置。

解出每一行的dp[m]，计算前缀和，枚举出一个最优区间即可。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) (x).begin(), (x).end()
const int N = 2e5 + 10;
int a[110][N], b[N], ans[N];
void solve() {
    int n,m,k,d;
    cin>>n>>m>>k>>d;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
        }
    }
    vector<int>ans;
    for(int i=1;i<=n;i++){
        deque<int>dq;
        vector<int> dp(m+10);
        dp[1]=1;
        dq.push_back(1);
        for(int j=2;j<=m;j++){
            if(!dq.empty()&&j-dq.front()-1>d) dq.pop_front();
            dp[j]=dp[dq.front()]+a[i][j]+1;
            while(!dq.empty()&&dp[j]<=dp[dq.back()]) dq.pop_back();
            dq.push_back(j);
        }

        ans.push_back(dp[m]);
    }
    int res=1e9;
    for(int i=1;i<ans.size();i++) ans[i]+=ans[i-1];
    res=ans[k-1];
    for(int i=k;i<ans.size();i++) res=min(res,ans[i]-ans[i-k]);
    cout<<res<<endl;
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T=1;
    cin >> T;
    while (T--) solve();
    return 0;
}