题目大意
在第 \((i,j)\) 个格子修建一个桥墩需要 \(a_{i,j}+1\) 的花费而且要求 \((i,0)\) 与 \((i,m)\) 必须修建桥墩并且桥墩之间的距离不得大于 \(d\)。现在需要求见 \(k\) 个连续的桥，求最小代价。
其中 \(1\le k\le n \le 100,3\le m\le 2\cdot 10,1\le d\le m\)。
思路
因为每一座桥修建的代价与其他桥是否修建无关，所以我们可以将每一座桥的修建代价求解出来，最终求出连续 \(k\) 座桥全部修建的最小值。
假设 \(f_i\) 表示在第 \(i\) 个位置修建桥墩而且 \(1\) 至 \(i-1\) 在修建则桥墩之后全部可以修桥的最小花费。
因为在第 \(i\) 个位置修建桥墩前，从 \(i-d-1\) 到 \(i-1\) 只要有一个修建桥墩就可以，所以状态转移方程如下：
\[f_i= \min_{j=i-d-1}^{i-1} f_j \]这样写的时间复杂度为 \(O(T\cdot nmd)\) 无法通过此题，可以考虑使用单点修改区间最小值查询线段树进行维护，这样时间复杂度就变成了 \(O(T\cdot nm \log d)\)。
AC Code
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5,INF=0x3f3f3f3f3f3f3f3f;
int n,m,num,d,a[N],f[N],s[N<<2],ans[N];
void change(int k,int l,int r,int x,int v) {
if(l==r&&l==x) {
s[k]=v;
return;
}
if(x<l||x>r) return;
int mid=(l+r)/2;
if(l<=x&&x<=mid) change(k*2,l,mid,x,v);
if(mid+1<=x&&x<=r) change(k*2+1,mid+1,r,x,v);
s[k]=min(s[k*2],s[k*2+1]);
}
int ask(int k,int l,int r,int x,int y) {
if(y<l||x>r) return INF;
if(x<=l&&r<=y) return s[k];
int mid=(l+r)/2;
return min(ask(k*2,l,mid,x,y),ask(k*2+1,mid+1,r,x,y));
}
void go(int number){
for(int i=1;i<=m;i++) cin>>a[i];
f[1]=1;
change(1,1,m,1,1);
for(int i=2;i<=m;i++){
f[i]=ask(1,1,m,max(i-d-1,1ll),max(i-1,1ll))+a[i]+1;
change(1,1,m,i,f[i]);
}
ans[number]=f[m];
}
void solve(){
cin>>n>>m>>num>>d;
for(int i=1;i<=n;i++) go(i);
for(int i=1;i<=n;i++) ans[i]+=ans[i-1];
int sum=INF;
for(int i=1;i+num-1<=n;i++) sum=min(sum,ans[i+num-1]-ans[i-1]);
cout<<sum<<'\n';
}signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
int T;cin>>T;
while(T--) solve();
return 0;
}