【poj3375】 Network Connection

题意

　　有$M$个网络接口和$N$台计算机，给出它们的坐标（在同一直线上），一个接口只能接一台计算机，费用为两坐标之差的绝对值，问最小费用为多少。

Solution

　　$f[i][j]$表示前$i$台计算机连在前$j$个网络接口上的最小费用。转移：$$f[i][j]=min(f[i][j-1],f[i-1][j-1]+|X[i]-X[j]|)$$

　　考虑$m$的范围很大，肯定有很多是无用的，我们找到距离$i$最近的接口$pos$，从$N-pos$ for到$N+pos$即可。

细节

代码

// poj3375

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<cmath>

#define LL long long

#define inf (1ll<<60)

#define Pi acos(-1.0)

#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);

using namespace std;

const int maxn=200010;

int t1[maxn],t2[maxn],pos[maxn],n,m;

LL f[2][maxn];

int main() {

	scanf("%d%d",&m,&n);

	for (int i=1;i<=m;i++) scanf("%d",&t2[i]);

	for (int i=1;i<=n;i++) scanf("%d",&t1[i]);

	sort(t1+1,t1+n+1);

	sort(t2+1,t2+m+1);

	for (int i=1;i<=n;i++) pos[i]=lower_bound(t2+1,t2+1+m,t1[i])-t2;

	memset(f,0x7f,sizeof(f));

	for (int i=0;i<=m;i++) f[0][i]=0;

	int p=0,q=1,l,r,u=0,v=m;

	for (int i=1;i<=n;i++) {

		l=max(1,pos[i]-n),r=min(m,pos[i]+n);

		p^=1,q^=1;

		for (int j=l;j<=r;j++) f[p][j]=min(f[p][j-1],f[q][min(j-1,v)]+abs(t1[i]-t2[j]));

		for (int j=u;j<=v;j++) f[q][j]=inf;

		u=l,v=r;

	}

	printf("%lld",f[p][r]);

	return 0;

}

巴特西

【poj3375】 Network Connection

题意

Solution

细节

代码

最新文章

热门文章