麻烦 dalao 帮忙看看数据合法性,以及我挂哪了。
Code:
```cpp
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
#include<initializer_list>
static char buf[1000000],*p1=buf,*p2=buf,obuf[1000000],*p3=obuf;
#define flush() fwrite(obuf,p3-obuf,1,stdout)
#define getchar() p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++
#define putchar(x) (p3-obuf<1000000)?(*p3++=x):(flush(),p3=obuf,*p3++=x)
#define end() (flush(),exit(0))
template<typename T> inline void read(T& x);
template<typename T> inline void write(T x);
inline void write(char x);
inline void write(const char* x);
template<typename... Args> inline void read(Args& ...args);
template<typename... Args> inline void write(Args ...args);
template<typename Type> const Type& min(const Type& x,const Type& y){return x<y?x:y;}
const int N=20005,M=205,Inf=0x3f3f3f3f;
int n,m;
int d[N],c[N],s[N],w[N],l[N],r[N];
int dp[N],cost[N];
std::vector<int> v[N];
class SegmentTree{
private:
struct node{
int val,lazy;
};
node tr[N<<2];
void push_up(const int& rt){
tr[rt].val=min(tr[rt<<1].val,tr[rt<<1|1].val);
}
void push_down(const int& rt){
if(tr[rt].lazy){
tr[rt<<1].lazy+=tr[rt].lazy,tr[rt<<1|1].lazy+=tr[rt].lazy;
tr[rt<<1].val+=tr[rt].lazy,tr[rt<<1|1].val+=tr[rt].lazy;
tr[rt].lazy=0;
}
}
void build(const int& rt,const int& l,const int& r){
tr[rt].lazy=0;
if(l==r){
tr[rt].val=dp[l];
return;
}
const int mid=(l+r)>>1;
build(rt<<1,l,mid),build(rt<<1|1,mid+1,r);
push_up(rt);
}
void updata(const int& rt,const int& l,const int& r,const int& L,const int& R,const int & Val){
if(L<=l&&r<=R){
tr[rt].lazy+=Val,tr[rt].val+=Val;
return;
}
push_down(rt);
const int mid=(l+r)>>1;
if(L<=mid&&R>mid) updata(rt<<1,l,mid,L,R,Val),updata(rt<<1|1,mid+1,r,L,R,Val);
else L<=mid?updata(rt<<1,l,mid,L,R,Val):updata(rt<<1|1,mid+1,r,L,R,Val);
push_up(rt);
}
int query(const int& rt,const int& l,const int& r,const int& L,const int& R){
if(L<=l&&r<=R) return tr[rt].val;
const int mid=(l+r)>>1;
push_down(rt);
if(L<=mid&&R>mid) return min(query(rt<<1,l,mid,L,R),query(rt<<1|1,mid+1,r,L,R));
else return L<=mid?query(rt<<1,l,mid,L,R):query(rt<<1|1,mid+1,r,L,R);
}
public:
void build(){build(1,1,n);}
void updata(int L,int R,int Val){if(L<R) updata(1,1,n,L,R,Val);}
int query(int L,int R){return query(1,1,n,L,R);}
};
SegmentTree tr;
signed main(){
read(n,m);
for(int i=2;i<=n;++i) read(d[i]);
for(int i=1;i<=n;++i) read(c[i]);
for(int i=1;i<=n;++i) read(s[i]);
for(int i=1;i<=n;++i) read(w[i]);
++n,++m;
d[n]=w[n]=Inf;
for(int i=1;i<=n;++i){
l[i]=std::lower_bound(d+1,d+n+1,d[i]-s[i])-d;
r[i]=std::lower_bound(d+1,d+n+1,d[i]+s[i])-d;
r[i]-=(d[i]+s[i]<d[r[i]]);
v[r[i]].emplace_back(i);
}
int ans=0;
for(int i=1;i<=n;++i){
dp[i]=ans+c[i];
for(int it:v[i]) ans+=w[it];
}
ans=dp[n];
for(int j=2;j<=m;++j){
tr.build();
for(int i=1;i<=n;++i){
if(i>1) dp[i]=tr.query(1,i-1)+c[i];
else dp[i]=c[i];
for(int it:v[i]) tr.updata(1,l[it]-1,w[it]);
}
ans=min(ans,dp[n]);
}
write(ans);
end();
}
template<typename T> inline void read(T& x){
x=0;bool flag=0;char ch=getchar();
for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') flag=1;
if(flag) for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)-(ch&15);
else for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+(ch&15);
}
template<typename T> inline void write(T x){
static char sta[40];
int top=0;
if(x<0){
putchar('-');
do sta[top++]=((-x)%10)^48,x/=10;
while(x);
}
else{
do sta[top++]=(x%10)^48,x/=10;
while(x);
}
while(top) putchar(sta[--top]);
}
inline void write(char x){putchar(x);}
inline void write(const char* str){while(*str!='\0') putchar(*str++);}
template<typename... Args> inline void read(Args& ...args){(void)std::initializer_list<int>{(read(args),0)...};}
template<typename... Args> inline void write(Args ...args){(void)std::initializer_list<int>{(write(args),0)...};}
```
by LQ2024 @ 2023-01-31 08:00:12
L<=R
by zyxawa @ 2023-01-31 08:07:46
解决了,谢谢。@[duguca](/user/673294)
by LQ2024 @ 2023-01-31 08:08:45
数据有够水的(恼)
by LQ2024 @ 2023-01-31 08:09:08