https://codeforc.es/problemset/problem/1216/F
有直线上 n 个位置, 每个位置上可以花费 i 的代价使得联网, 某些位置可以放置路由器, 放路由器的代价也是 i, 放置了路由器以后, 可以让 [i-k,i+k] 的范围内上网, 要求每台电脑都可以上网, 最少需要多少代价.
思路: 动态规划 + 贪心 + 线段树维护
f[i]表示前 i 个电脑上网所需要的最小费用.
转移的时候分为两种情况.
1. 第 i 台电脑独立上网, 花费的代价是 i
f[i-1]+i
2 第 i 台电脑通过前面某台电脑的路由器上网, 根据贪心的原则, 肯定是在 [i-k,i-1] 里面位置最小的可以放路由器的地方, 一来覆盖的范围可以更大, 二来费用更低.
我们可以通过线段树里面维护这个位置, 二分来查找.
转移的时候, 注意由于区间可以重叠, 所以我们要求一个区间最小值来进行转移, 还是用线段树来做.
- #include<bits/stdc++.h>
- using namespace std;
- #define LL long long
- #define lc (x<<1)
- #define rc (x<<1|1)
- #define mid (l+r)/2
- int const N=200000+10;
- char s[N];
- LL f[N],v[N<<2];
- int n,k,sum[N<<2],pos[N<<2];
- void build(int x,int l,int r){
- if(l==r){
- sum[x]=s[l]=='1';
- if(sum[x]) pos[x]=l;
- return ;
- }
- build(lc,l,mid);
- build(rc,mid+1,r);
- sum[x]=sum[lc]+sum[rc];
- if(pos[lc]) pos[x]=pos[lc];
- else pos[x]=pos[rc];
- }
- int query(int x,int l,int r,int ll,int rr){
- if(ll<=l && r<=rr){
- return pos[x] ;
- }
- int t1=0,t2=0;
- if(ll<=mid) t1=query(lc,l,mid,ll,rr);
- if(t1) return t1;
- if(rr>mid) t2=query(rc,mid+1,r,ll,rr);
- return t2;
- }
- void insert(int x,int l,int r,int p,LL tv){
- if(l==r){
- v[x]=tv;
- return;
- }
- if(p<=mid) insert(lc,l,mid,p,tv);
- else insert(rc,mid+1,r,p,tv);
- v[x]=min(v[lc],v[rc]);
- }
- LL ask(int x,int l,int r,int ll,int rr){
- if(ll>rr) return 1e18;
- if(ll<=l && r<=rr) {
- return v[x];
- }
- LL res=1e18;
- if(ll<=mid) res=min(res,ask(lc,l,mid,ll,rr));
- if(rr>mid) res=min(res,ask(rc,mid+1,r,ll,rr));
- return res;
- }
- int main(){
- scanf("%d%d",&n,&k);
- scanf("%s",s+1);
- build(1,1,n);
- for(int i=1;i<=n;i++){
- f[i]=f[i-1]+i;
- int t=query(1,1,n,max(1,i-k),i);
- if(t) {
- int p=max(1,t-k-1);
- LL tmp=ask(1,1,n,p,i-1);
- if(t-k-1<1) tmp=0;
- f[i]=min(f[i],tmp+t);
- }
- insert(1,1,n,i,f[i]);
- }
- cout<<f[n]<<endl;
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-3216454.html