ZJOI2010 基站选址

题目链接：https://www.luogu.com.cn/problem/P2605

题目的条件数据比较多，在一个地方建基站会影响左右两边
看看数据范围，考虑$dp$
因为基站会影响左右两边，设$dp[i][j]$表示在前$j$个村庄中建$i$个基站,且最后一个基站建在第$j$个位置,$val(i,j)$代表$i$至$j$间村庄$w$的花费（注意：$j$代表村庄）
$$dp[i][j]=min(dp[i-1][k]+val(k,i))$$
直接dp肯定会爆
重点在于如何维护$val(k,j)$
$val(i,j)$不具有单调性，考虑用数据结构维护
考虑任意结点$x$的$w[x]$对答案的贡献
发现是从1开始的一段连续区间，保证$d[x]-d[k]>s[x]$
再看看$dp$方程，发现$k<=100$(题目中)想到可能会用到线段树
第一维枚举$k$（建站个数）变量为$i$
将$i-1$的$dp$值建一棵线段树
第j个结点代表$dp[i-1][j-1]$
在从$1$枚举到$n$，枚举到$j$单点加入$x$,保证$d[j]-d[x]>=s[x]$
找出满足$d[x]-d[k]>s[x]$的区间,区间修改
注意：$x$的顺序不一定是原数组(被害调1.5h)
然后是根据$dp$方程区间查询
最后找答案我是重新建树 强行增大常数
就可以了
时间复杂度$O(knlogn)$

$Code$

#include 
using namespace std;
#define int long long
const int MAXN=2e4,MAXK=100,inf=1e15;
struct SEG{int l,r,mn,tag;
}tree[MAXN<<2|10];
int dp[MAXK+10][MAXN+10];
int d[MAXN+10],c[MAXN+10],s[MAXN+10],w[MAXN+10],lx[MAXN+10];
//lx[i]代表i前面建基站能覆盖到i的最远村庄
struct ww{int op,val;
}q[MAXN+10];    //q为单点加入x的顺序
inline int read();
inline bool cmp(const ww&,const ww&);
inline void pushup(int);
inline void pushdown(int);
void build(int,int,int,int);
void update(int,int,int,int);
int query(int,int,int);signed main(){//freopen ("std.in","r",stdin);//freopen ("std.out","w",stdout);int n,k;n=read(),k=read();for (register int i=1;i<n;++i)	d[i+1]=read();for (register int i=1;i<=n;++i)	c[i]=read();for (register int i=1;i<=n;++i)	s[i]=read(),q[i].val=d[i]+s[i],q[i].op=i;for (register int i=1;i<=n;++i)	w[i]=read(),dp[0][i]=inf;for (register int i=1;i<=n;++i)	lx[i]=lower_bound(d+1,d+i,d[i]-s[i])-d;sort(q+1,q+n+1,cmp);int l,ans=inf;for (register int i=1;i<=k;++i){dp[i][0]=inf;l=1;build(i-1,1,n,1);for (register int j=1;j<=n;++j){while (l<j && d[j]-d[q[l].op]>s[q[l].op])	update(1,lx[q[l].op],1,w[q[l].op]),++l;    //加入覆盖不到的点的贡献dp[i][j]=query(1,j,1)+c[j];    //更新dp值}//统答案ans=min(ans,dp[i][n]);build(i,1,n,1);for (register int j=1;j<=n;++j)	update(1,lx[j],1,w[j]);ans=min(query(1,n,1),ans);}printf("%lld\n",ans);return 0;
}inline int read(){int x=0;char c=getchar();while (!isdigit(c))c=getchar();while (isdigit(c))x=(x<<1)+(x<<3)+(c&15),c=getchar();return x;
}inline bool cmp(const ww &x,const ww &y){return x.val<y.val;
}inline void pushup(int s){tree[s].mn=min(tree[s<<1].mn,tree[s<<1|1].mn);
}inline void pushdown(int s){int val=tree[s].tag;tree[s<<1].mn+=val;tree[s<<1].tag+=val;tree[s<<1|1].mn+=val;tree[s<<1|1].tag+=val;tree[s].tag=0;
}void build(int k,int l,int r,int s){tree[s].l=l,tree[s].r=r,tree[s].tag=0;if (l==r){tree[s].mn=dp[k][l-1];return;}int mid=l+r>>1;build(k,l,mid,s<<1);build(k,mid+1,r,s<<1|1);pushup(s);
}void update(int l,int r,int s,int val){if (tree[s].l>r || tree[s].r<l)	return;if (l<=tree[s].l && tree[s].r<=r){tree[s].mn+=val;tree[s].tag+=val;return;}pushdown(s);update(l,r,s<<1,val);update(l,r,s<<1|1,val);pushup(s);
}int query(int l,int r,int s){if (tree[s].l>r || tree[s].r<l)	return inf;if (l<=tree[s].l && tree[s].r<=r)	return tree[s].mn;pushdown(s);return min(query(l,r,s<<1),query(l,r,s<<1|1));
}

将$x$的更新顺序直接和原数组相同的错误数据
输入：

8 2
2 3 11 16 17 18 21 
4 3 14 2 5 14 6 10 
10 9 4 4 9 7 5 3 
6 10 11 9 8 13 6 7 

正确输出：

18

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！