题意：
戳这里查看
分析：
我们发现题目里面每一个建立的基站可能会对之前的状态有所影响，所以我们在设计DP状态时需要将这种影响消除掉
我们设
f
[
i
]
[
j
]
f[i][j]
f[i][j]表示在第
i
i
i个村庄修建第
j
j
j个基站且不考虑对
[
i
+
1
，
n
]
[i+1，n]
[i+1，n]个村庄的影响时的最小费用
转移方程就是
f
[
i
]
[
j
]
=
m
i
n
(
f
[
k
]
[
j
−
1
]
+
c
o
s
t
[
k
]
[
i
]
+
c
[
i
]
)
f[i][j]=min(f[k][j-1]+cost[k][i]+c[i])
f[i][j]=min(f[k][j−1]+cost[k][i]+c[i])，其中
c
o
s
t
[
k
]
[
i
]
cost[k][i]
cost[k][i]表示在
i
,
k
i,k
i,k建立基站后，
[
k
+
1
,
i
−
1
]
[k+1,i-1]
[k+1,i−1]内没有被覆盖的村庄赔付的和值，这样的DP复杂度是
O
(
n
2
k
)
O(n^2k)
O(n2k)我们考虑怎么优化，首先可以滚动数组滚掉一维，
f
[
i
]
=
m
i
n
(
f
[
k
]
+
c
o
s
t
[
k
]
[
i
]
)
+
c
[
i
]
f[i]=min(f[k]+cost[k][i])+c[i]
f[i]=min(f[k]+cost[k][i])+c[i]然后我们发现对于
c
o
s
t
[
k
]
[
i
]
cost[k][i]
cost[k][i]来说，每个村庄的贡献时独立的，我们记
l
e
f
[
i
]
,
r
i
g
[
i
]
lef[i],rig[i]
lef[i],rig[i]表示每一个村庄能接受信号的左右边界，那么对于第
i
i
i个村庄安装基站时，从
[
1
,
l
e
f
[
k
]
−
1
]
[1,lef[k]-1]
[1,lef[k]−1]转移来的状态必定会赔付村庄
k
k
k的费用也就是说我们我们需要一个支持区间修改，区间查询最小值的数据结构，所以我们用线段树维护
f
[
k
]
+
c
o
s
t
[
k
]
[
i
]
f[k]+cost[k][i]
f[k]+cost[k][i]（此时
i
i
i是在外层枚举的，线段树只要维护
k
k
k的信息就可以了），复杂度
O
(
n
l
o
g
n
k
)
O(nlog_nk)
O(nlognk)
代码：
#include<bits/stdc++.h>
using namespace std
;
namespace zzc
{
const int maxn
= 2e4+5;
const int inf
= 0x3f3f3f3f;
int n
,k
,ans
;
int c
[maxn
],w
[maxn
],s
[maxn
],f
[maxn
],d
[maxn
],lef
[maxn
],rig
[maxn
],val
[maxn
<<3],tag
[maxn
<<3];
vector
<int> pos
[maxn
];
void pushup(int x
)
{
val
[x
]=min(val
[x
<<1],val
[x
<<1|1]);
}
void pushdown(int x
)
{
if(!tag
[x
]) return ;
tag
[x
<<1]+=tag
[x
];
tag
[x
<<1|1]+=tag
[x
];
val
[x
<<1]+=tag
[x
];
val
[x
<<1|1]+=tag
[x
];
tag
[x
]=0;
}
void build(int rt
,int l
,int r
)
{
tag
[rt
]=0;
if(l
==r
)
{
val
[rt
]=f
[l
];
return ;
}
int mid
=(l
+r
)>>1;
build(rt
<<1,l
,mid
);
build(rt
<<1|1,mid
+1,r
);
pushup(rt
);
}
void update(int rt
,int l
,int r
,int ll
,int rr
,int v
)
{
if(l
>r
) return ;
if(l
>=ll
&&r
<=rr
)
{
val
[rt
]+=v
;
tag
[rt
]+=v
;
return ;
}
pushdown(rt
);
int mid
=(l
+r
)>>1;
if(ll
<=mid
) update(rt
<<1,l
,mid
,ll
,rr
,v
);
if(mid
<rr
) update(rt
<<1|1,mid
+1,r
,ll
,rr
,v
);
pushup(rt
);
}
int query(int rt
,int l
,int r
,int ql
,int qr
)
{
if(ql
>qr
) return inf
;
if(l
>=ql
&&r
<=qr
) return val
[rt
];
pushdown(rt
);
int mid
=(l
+r
)>>1;
int res
=inf
;
if(ql
<=mid
) res
=min(res
,query(rt
<<1,l
,mid
,ql
,qr
));
if(mid
<qr
) res
=min(res
,query(rt
<<1|1,mid
+1,r
,ql
,qr
));
return res
;
}
void work()
{
ios
::sync_with_stdio(false);
cin
>>n
>>k
;k
++;
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
++;w
[n
]=d
[n
]=inf
;
for(int i
=1;i
<=n
;i
++)
{
lef
[i
]=lower_bound(d
+1,d
+n
+1,d
[i
]-s
[i
])-d
;
rig
[i
]=lower_bound(d
+1,d
+n
+1,d
[i
]+s
[i
])-d
;
if(d
[rig
[i
]]>d
[i
]+s
[i
]) rig
[i
]--;
pos
[rig
[i
]].push_back(i
);
}
for(int i
=1;i
<=k
;i
++)
{
if(i
==1)
{
int res
=0;
for(int j
=1;j
<=n
;j
++)
{
f
[j
]=res
+c
[j
];
for(int l
=0;l
<pos
[j
].size();l
++) res
+=w
[pos
[j
][l
]];
}
ans
=f
[n
];
}
else
{
build(1,1,n
);
for(int j
=1;j
<=n
;j
++)
{
f
[j
]=query(1,1,n
,1,j
-1)+c
[j
];
for(int l
=0;l
<pos
[j
].size();l
++) if(lef
[pos
[j
][l
]]>1) update(1,1,n
,1,lef
[pos
[j
][l
]]-1,w
[pos
[j
][l
]]);
}
ans
=min(ans
,f
[n
]);
}
}
cout
<<ans
<<endl
;
}
}
int main()
{
zzc
::work();
return 0;
}
