题目大意

在第 $(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;
}