单调队列优化dp

题目传送门

大致思路

很明显各行的最小花费相互独立,可以分别计算,最后求前缀和,枚举端点即可得出答案,主要难点在于求单独一行的最小花费:
记 $dp_{i}$ 为只考虑前 $i$ 列,且第 $i$ 列建桥墩的最小花费

$$dp_{i}=a_i+1+\sum_{j=i-d-1}^{i-1}min\{dp_j\} $$

直接一点时间复杂度为$O(nmd)$,考虑单调队列优化,优化后 $O(nm)$
优化具体细节看代码

void solve() {
    int n,m,k,d;
    cin >> n >>m >> k >> d;
    vector<vector<int>>a(n+1,vector<int>(m+1));
    for (int i=1;i<=n;i++) {
        for (int j=1;j<=m;j++) cin >> a[i][j];
    }
    vector<int> ans(n+1);
    for (int i=1;i<=n;i++) {
        vector<int> dp(m+1);
        deque<int> q;
        dp[1]=a[i][1]=a[i][1]+1;//初始化
        q.push_front(1);
        for (int j=2;j<=m;j++) {
            while (!q.empty() && j-q.front()-1>d) q.pop_front();//队首节点与当前节点距离超过d,不考虑
            dp[j]=a[i][j]+1+dp[q.front()];
            while (!q.empty() && dp[j]<=dp[q.back()]) q.pop_back();//队尾不如当前dp值优秀,out
            q.push_back(j);
        }
        ans[i]=dp[m];
    }
    vector<int> s(n+1);
    for (int i=1;i<=n;i++) s[i]=s[i-1]+ans[i];
    int mn=LLONG_MAX;
    for (int i=1;i+k-1<=n;i++) mn=min(mn,s[i+k-1]-s[i-1]);
    cout << mn <<el;
}