思路

可以发现此题与仓库建设很像，没做过的可以去做一下。
回到这道，令 $sumnum_i=\sum\limits_{k=0}^i d_k$ 和 $sum_i=sum_{i-1}+sumnum_{i-1}$ 其中 $sumnum_i$ 表示到 $i$ 这个位置共有多少人，然后 $sum_i$ 表示 $i$ 以前的人到 $i$ 的总距离。可以得出一个 Dp 方程 $dp_{i,t}=\min\limits_{k=0}^i(dp_{k,t-1}+sum_i-sum_k-sumnum_k\times (i-k))$ 。可以发现直接枚举肯定要超时，但是整理一下方程可得 $dp_{i,t}=sum_i+\min\limits_{k=0}^i(-sumnum_k\times i+sumnum_k\times k-sum_k+dp_{k,t-1})$ 可以发现很像一个一次函数，所以使用斜率优化。
使用李超线段树维护最小值即可。

Code

CPP

#include<bits/stdc++.h>
#define int long long
#define endl "\n"
#define f(i,j,k) for(int i=j;i<=k;i++)
#define F(i,j,k) for(int i=j;i>=k;i--)
using namespace std;
const int maxn=1e6+10,inf=LLONG_MAX;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
inline void write(int x){
	if(x<0) {x=~(x-1); putchar('-');}
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
int n=read(),L=read(),root=1,dp[maxn][5],sum[maxn],sum_num[maxn],dis[maxn/10],tree[maxn<<2];
struct line{int k,b;} a[maxn];
inline int getY(int id,int X){return a[id].k*X+a[id].b;}
inline void update(int rt,int l,int r,int id){
	if(l==r){
		if(getY(id,l)<getY(tree[rt],l)) tree[rt]=id;
		return ;
	}
	int mid=(l+r)>>1;
	if(getY(id,mid)<getY(tree[rt],mid)) swap(tree[rt],id);
	if(getY(id,l)<getY(tree[rt],l)) update(rt<<1,l,mid,id);
	else if(getY(id,r)<getY(tree[rt],r)) update(rt<<1|1,mid+1,r,id);
}
inline int query(int rt,int l,int r,int X){
	if(!rt) return inf;
	if(l==r) return getY(tree[rt],X);
	int mid=(l+r)>>1;
	if(X<=mid) return min(getY(tree[rt],X),query(rt<<1,l,mid,X));
	else return min(getY(tree[rt],X),query(rt<<1|1,mid+1,r,X));
}
inline void work(){
	update(root,0,L,L+1); f(i,1,n) dis[i]=read(),sum_num[dis[i]]+=read();
	f(i,1,L) sum_num[i]+=sum_num[i-1],sum[i]=sum[i-1]+sum_num[i-1];
	f(j,1,4){
		f(i,1,L) dp[i][j]=query(root,0,L,i)+sum[i];
		memset(tree,0,sizeof(tree)); root=1; update(root,0,L,L+1); 
		f(i,1,L) a[i]=(line){-sum_num[i],sum_num[i]*i-sum[i]+dp[i][j]},	update(root,0,L,i);
	} write(dp[L][4]);
}
signed main(){work();return !!!!!("YZren");}

题解：P8632 [蓝桥杯 2015 国 B] 居民集会

文章操作

思路

Code

相关推荐

评论

题解：P8632 [蓝桥杯 2015 国 B] 居民集会