Haokee Note

CF1941E Rudolf and k Bridges

2 min read

前缀和 序列dp 单调队列

首先每一行需要花费的成本是不变的，而这里是选择连续的 行，因此可以使用前缀和优化。那么我们就需要对每一行求解。

假设当前行的数组为 ，那么设 表示为修桥修到 的成本，这个值就等于所有距离小于等于 的 ，当中 的最小值加上 。但是这题 ，因此我们需要使用单调队列优化。由于好渴鹅懒得写单调队列，因此直接使用优先队列。

时间复杂度 。

#include <iostream>
#include <utility>
#include <queue>
 
using namespace std;
using LL = long long;
 
const LL kMaxN = 105, kMaxM = 2e5 + 5;
 
LL a[kMaxN][kMaxM], dp[kMaxM], p[kMaxN], t, n, m, k, d, ans;
priority_queue<pair<LL, LL>, vector<pair<LL, LL>>, greater<>> q;
 
void solve(LL x) {
  for (; q.size(); q.pop()) { }
  q.emplace(a[x][1] + 1, 1);
  for (LL i = 2; i <= m; i++) {
    for (; q.top().second < i - d - 1; q.pop()) { }
    q.emplace(q.top().first + a[x][i] + 1, i);
  }
  for (; q.top().second != m; q.pop()) { }
  p[x] = q.top().first;
}
 
int main() {
  for (cin >> t; t; t--) {
    cin >> n >> m >> k >> d;
    ans = 1e18;
    for (LL i = 1; i <= n; i++) {
      for (LL j = 1; j <= m; j++) {
        cin >> a[i][j];
      }
    }
    for (LL i = 1; i <= n; i++) {
      solve(i);
      p[i] += p[i - 1];
    }
    for (LL i = k; i <= n; i++) {
      ans = min(ans, p[i] - p[i - k]);
    }
    cout << ans << '\n';
  }
  return 0;
}

Graph View