线段树优化线性dp
拿到一道题目直接大力dp，设dp[i][j]表示考虑到第i个点并将其选中，且已经选了j个点的最优解，cost[i][j]表示选了i，j，之间的代价，显然可以压维：
[dp[i] = max (dp[k] + cost[k][i] ) +c[i] (j-1<=k<i)
]
但这个时间复杂度我们根本无法接受qwq，时间不够，数据结构来凑
我们考虑：记录每个点能够受到的基站的范围l,r，并且用vector记录第i个点能够影响的点j（i是j点的右端点）。首先，有一个套路就是建一个虚点：n+1，因为我们dp是强制选第i个点，所以要加入一个虚点方便统计答案。每次从 1 - i枚举，求出1 - i-1的最小值，并将该点带来的影响加入。加入的影响就是
rep(k,0,(int)(v[i].size()-1)){update(1,1,n,1,nl[v[i][k]]-1,cost[v[i][k]]);}
//nl[i]代表能影响到i点的最做的位置
code:
#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<set>
#include<map>
#include<vector>
#define maxn 50000
#define int long long
#define SZJ signed
#include<time.h>
#define AK main
#define half (l+r)>>1
#define SDOI ()
using namespace std;
#define rep(i,a,b) for (int i=a;i<=b;++i)
#define dep(i,a,b) for (int i=a;i>=b;i--)
#define erpe (i,a) for (int i=head[a];i!=-1;i=e[i].next)
#define lson t[s].lc
#define rson t[s].rc
int dp[maxn],n,k,sum[maxn],w[maxn],cf[maxn],cost[maxn],dis[maxn],nl[maxn],tot,fa[maxn],nr[maxn];
struct hzw
{
int lc,rc,mx,tag;
}t[maxn*4];
vector<int>v[maxn];
inline void build(int s,int l,int r)
{
t[s].tag=0;
if (l==r)
{
t[s].mx=dp[l];
return;
}
int mid=half;
t[s].lc=++tot;
build(tot,l,mid);
t[s].rc=++tot;
build(tot,mid+1,r);
t[s].mx=min(t[lson].mx,t[rson].mx);
}
inline void pushdown(int s)
{
t[lson].mx+=t[s].tag,t[lson].tag+=t[s].tag;
t[rson].mx+=t[s].tag,t[rson].tag+=t[s].tag;
t[s].tag=0;
}
inline void update(int s,int l,int r,int cl,int cr,int x)
{
if (cl>cr) return;
if (l==cl&&r==cr)
{
t[s].mx+=x;
t[s].tag+=x;
return;
}
int mid=half;
if (t[s].tag) pushdown(s);
if (cr<=mid) update(lson,l,mid,cl,cr,x);
else if (cl>mid) update(rson,mid+1,r,cl,cr,x);
else
{
update(lson,l,mid,cl,mid,x);
update(rson,mid+1,r,mid+1,cr,x);
}
t[s].mx=min(t[lson].mx,t[rson].mx);
}
inline int query(int s,int l,int r,int cl,int cr)
{
if (cl>cr) return 0;
if (l==cl&&r==cr)
{
return t[s].mx;
}
int mid=half;
if (t[s].tag) pushdown(s);
if (cr<=mid) return query(lson,l,mid,cl,cr);
else if (cl>mid) return query(rson,mid+1,r,cl,cr);
else
{
return min(query(lson,l,mid,cl,mid),query(rson,mid+1,r,mid+1,cr));
}
}
SZJ AK SDOI
{
cin>>n>>k;
rep (i,2,n) scanf("%lld",&dis[i]);
rep (i,1,n) scanf("%lld",&w[i]);
rep (i,1,n) scanf("%lld",&fa[i]);
rep (i,1,n) scanf("%lld",&cost[i]);
rep (i,1,n) sum[i]=sum[i-1]+cost[i];
dis[++n]=1e17;
rep (i,1,n)
{
nl[i]=lower_bound(dis+1,dis+1+n,dis[i]-fa[i])-dis;
nr[i]=lower_bound(dis+1,dis+1+n,dis[i]+fa[i])-dis;
if (dis[i]+fa[i]<dis[nr[i]]) nr[i]--;
v[nr[i]].push_back(i);
}
int tmp=0;
rep (i,1,n)
{
dp[i]=tmp+w[i];
for (int j=0;j<v[i].size();++j) tmp+=cost[v[i][j]];
}
int ans=dp[n];
rep (j,2,k)
{
tot=1;
build(1,1,n);
rep (i,1,n)
{
dp[i]=query(1,1,n,1,i-1)+w[i];
rep(k,0,(int)(v[i].size()-1)){update(1,1,n,1,nl[v[i][k]]-1,cost[v[i][k]]);}
}
ans=min(ans,dp[n]);
}
cout<<ans;
}