题目大意：给一个行为n列为m的河流二维数组，数字代表河流的深度。题目要求连续建造k座桥，桥的定义是从第一列到第m列，每隔d需要按照支架，安装支架的代价是深度+1。问安装最少需要多少代价？
思路：单调队列优化dp，dp数组只需要一维，dp[i]的含义是从1到i建桥的最小代价。因为在i安装支架，那么上一个支架可以安装的地方就是[i-d-1,i-1]，那么dp[i]=min(dp[i-1],dp[i-2],dp[i-3].....dp[i-d-1]+这个点的代价+1，但是这样明显会超时。那么就可以使用单调队列来优化中间找最小值的过程。
#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define endl '\n'
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pii;
const int N=1e6+10,mod=1e9+7;
ld pi=acos(-1.0);
int main()
{
ios::sync_with_stdio(NULL);cin.tie(0),cout.tie(0);
ll t;cin>>t;
while(t--)
{
ll n,m,k,d;cin>>n>>m>>k>>d;
ll min1=1e18;
vector<ll> ans(n+10);
vector<ll> mp(m+10);
for(int i=1;i<=n;i++)
{
vector<ll> dp(m+10);
for(int j=1;j<=m;j++)
{
cin>>mp[j];
}
dp[1]=1;//第一个点需要建立一个支架，并且第一个点的深度都是0，那么代价就是1
deque<ll> op;
for(int j=1;j<=m;j++)
{
while(op.size()&&j-op.front()-1>d)op.pop_front();//如果单调队列里面的下标和当前点相差大于d+1就要舍弃
if(op.size())dp[j]=dp[op.front()]+mp[j]+1;//从上一个最小值转移过来
while(op.size()&&dp[j]<=dp[op.back()])op.pop_back();//如果当前的dp值比之前优，那么就可以将之前的舍弃 保证从相差不大于d+1的最小代价转移
op.push_back(j);
// cout<<dp[j]<<' ';
}
// cout<<endl;
ans[i]=dp[m];
}
//求连续的k个桥的最小代价
for(int i=1;i<=n;i++)
{
ans[i]+=ans[i-1];//前缀和优化，本题数据不大暴力可以过
}
for(int i=k;i<=n;i++)
{
min1=min(min1,ans[i]-ans[i-k]);
}
cout<<min1<<endl;
}
return 0;
}