LA4273 Post Offices

题目戳这里。

村庄排序。状态\(f[j][i]\)表示考虑前\(i\)个村庄，造\(j\)个邮局且\(i\)造了邮局的最小代价。我们用\(Lb_i,Rb_i\)表示在第\(i\)个村庄造邮局，邮局最左和最右能够服务到的村庄。\(pre_i\)表示\(P\)的前缀和。

\[f[j][i] = C_i + \left\{
\begin{array}{ll}
\min (f[j-1][k]) & Rb_k\ge Lb_i\\
\min (f[j-1][k]+pre_{Lb_i-1}-pre_{Rb_k}) & Rb_k < Lb_i
\end{array} \right.\]

按\(Rb_i\)来建线段树，分别维护\(f[j-1][k]\)和\(f[j-1][k]-pre_{Rb_k}\)最小值即可。

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cstdlib>

using namespace std;

const int maxn = 10010,maxm = 110; const int inf = 1<<30;

int N,M,X[maxn],C[maxn],R[maxn],Case,Lbound[maxn],Rbound[maxn],leaf[maxn];

int f[maxm][maxn],P[maxn],tree[4*maxn][2],ans;

inline int gi()

{

	char ch; int ret = 0,f = 1;

	do ch = getchar(); while (!(ch >= '0'&&ch <= '9')&&ch != '-');

	if (ch == '-') f = -1,ch = getchar();

	do ret = ret*10+ch-'0',ch = getchar(); while (ch >= '0'&&ch <= '9');

	return ret*f;

}

inline void build(int now,int l,int r,int i)

{

	if (l == r) { tree[now][0] = tree[now][1] = inf; leaf[l] = now; return; }

	int mid = (l+r) >> 1;

	build(now<<1,l,mid,i); build(now<<1|1,mid+1,r,i);

	tree[now][0] = tree[now][1] = inf;

}

inline void modify(int pos,int a,int b)

{

	if (a < tree[leaf[pos]][0])

	{

		tree[leaf[pos]][0] = a;

		for (int now = leaf[pos]>>1;now&&tree[now][0] > a;now >>= 1) tree[now][0] = a;

	}

	if (b < tree[leaf[pos]][1])

	{

		tree[leaf[pos]][1] = b;

		for (int now = leaf[pos]>>1;now&&tree[now][1] > b;now >>= 1) tree[now][1] = b;

	}

}

inline int query(int i,int now,int l,int r,int ql,int qr)

{

	if (l == ql&&r == qr) return tree[now][i];

	int mid = (l+r)>>1;

	if (qr <= mid) return query(i,now<<1,l,mid,ql,qr);

	else if (ql > mid) return query(i,now<<1|1,mid+1,r,ql,qr);

	else return min(query(i,now<<1,l,mid,ql,mid),query(i,now<<1|1,mid+1,r,mid+1,qr));

}

int main()

{

	freopen("4273.in","r",stdin);

	freopen("4273.out","w",stdout);

	while (++Case)

	{

		N = gi(); M = gi(); if (!N&&!M) break;

		printf("Case %d: ",Case);

		for (int i = 2;i <= N;++i) X[i] = gi();

		for (int i = 1;i <= N;++i) C[i] = gi();

		for (int i = 1;i <= N;++i) R[i] = gi();

		for (int i = 1;i <= N;++i) P[i] = gi()+P[i-1];

		for (int i = 1;i <= N;++i) Lbound[i] = lower_bound(X+1,X+N+1,X[i]-R[i])-X,Rbound[i] = upper_bound(X+1,X+N+1,X[i]+R[i])-X-1;

		ans = P[N];

		for (int i = 1;i <= N;++i) f[1][i] = C[i]+P[Lbound[i]-1],ans = min(ans,f[1][i]+P[N]-P[Rbound[i]]);

		for (int i = 2;i <= M;++i)

		{

			build(1,1,N,i-1);

			for (int j = i;j <= N;++j)

			{

				modify(Rbound[j-1],f[i-1][j-1],f[i-1][j-1]-P[Rbound[j-1]]);

				f[i][j] = query(0,1,1,N,Lbound[j],N);

				if (Lbound[j]-1) f[i][j] = min(f[i][j],query(1,1,1,N,1,Lbound[j]-1)+P[Lbound[j]-1]);

				f[i][j] += C[j];

				ans = min(ans,f[i][j]+P[N]-P[Rbound[j]]);

			}

		}

		cout << ans << endl;

	}

	fclose(stdin); fclose(stdout);

	return 0;

}

巴特西

LA4273 Post Offices

最新文章

热门文章