初始化 $f[0][i]$ 时。 为啥只有全设为 inf 是对的。

按照道理来说应该是谁都没有被覆盖，都应该求和费用啊。

求解答

#include<bits/stdc++.h>
#define int long long
#define ls u*2
#define rs u*2+1 
using namespace std;
const int N=2e4+10,M=110,inf=1e18;
typedef pair<int,int> PII;
struct Tree
{
	int l,r;
	int minv;
	int add;
}tr[N*4];
int f[N];
int d[N],c[N],s[N],w[N];
vector<PII> q[N];
int n,m;
int res;

void pushup(int u)
{
	tr[u].minv=min(tr[ls].minv,tr[rs].minv);
}

void trans(int u,int c)
{
	tr[u].minv+=c,tr[u].add+=c;
} 

void pushdown(int u)
{
	if(tr[u].add) trans(ls,tr[u].add),trans(rs,tr[u].add),tr[u].add=0;
}

void build(int u,int l,int r)
{
	tr[u]={l,r,f[l],0};
	if(l==r) return;
	int mid=l+r>>1;
	build(ls,l,mid),build(rs,mid+1,r);
	pushup(u); 
}

void modify(int u,int l,int r,int c)
{
	if(l>r) return;
	if(tr[u].l>=l&&tr[u].r<=r) trans(u,c);
	else
	{
		pushdown(u);
		int mid=tr[u].l+tr[u].r>>1;
		if(l<=mid) modify(ls,l,r,c);
		if(r>mid) modify(rs,l,r,c);
		pushup(u);
	}
}

int query(int u,int l,int r)
{
	if(tr[u].l>=l&&tr[u].r<=r) return tr[u].minv;
	pushdown(u);
	int mid=tr[u].l+tr[u].r>>1,res=inf;
	if(l<=mid) res=min(res,query(ls,l,r));
	if(r>mid) res=min(res,query(rs,l,r));
	return res; 
}

signed main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=2;i<=n;i++) cin>>d[i];
	for(int i=1;i<=n;i++) cin>>c[i];
	for(int i=1;i<=n;i++) cin>>s[i];
	for(int i=1;i<=n;i++) cin>>w[i];
	n++;
	d[n]=inf,c[n]=0,s[n]=0,w[n]=inf;
	
	for(int i=1;i<=n;i++)
	{
		int l=lower_bound(d+1,d+1+n,d[i]-s[i])-d;
		int r=upper_bound(d+1,d+1+n,d[i]+s[i])-d-1;
		q[r].push_back({l,i});
	}
	
	res=inf;
	for(int i=1;i<=n;i++) f[i]=f[i-1]+w[i];
	f[0]=0;
	m++;
	
	for(int k=1;k<=m;k++)
	{
		build(1,0,n);
		for(int i=1;i<=n;i++)
		{
			f[i]=query(1,0,i-1)+c[i];
			for(auto Q:q[i])
			{
				int l=Q.first,id=Q.second;
				modify(1,0,l-1,w[id]);
			}
		}
		res=min(res,f[n]);
	}
	
	cout<<res<<"\n";
	
	return 0;
}