有向直线2中值问题

有向直线2中值问题

时间: 1ms        内存:64M

描述:

给定一条有向直线L以及L上的n+1个点x0 < x1 < …… < xn。有向直线L上的每个点xi都有一个权w(xi);每条有向边(xi,xi-1)也都有一个非负边长d(xi,xi-1)。有向直线L上的每个点xi可以看作客户,其服务需求量为w(xi)。每条边(xi,xi-1)的边长d(xi,xi-1)可以看作运输费用。如果在点xi处未设置服务机构,则将点xi处的服务需求沿有向边转移到点xj处服务机构需付出的服务转移费用为w(xi)*d(xi,xj)。在点x0处已设置了服务机构,现在要在直线L上增设2处服务机构,使得整体服务转移费用最小。对于给定的有向直线L,计算在直线L上增设2处服务机构的最小服务转移费用。

输入:

输入数据的第1行有1个正整数n(n≤20000),表示有向直线L上除了点x0外还有n个点x0 < x1 < ……< xn。接下来的n行中,每行有2个整数。第i+1行的2个整数分别表示w(xn-i-1)和d(xn-i-1,xn-i-2)。

输出:

输出只有一个整数,表示最小服务转移费用。

示例输入:

9
1 2
2 1
3 3
1 1
3 2
1 6
2 1
1 2
1 1

示例输出:

26

提示:

参考答案(内存最优[1504]):

#include<iostream>
#include<stdio.h>
#include<limits.h>
using namespace std;
int dist[20005],swt[20005],wt[20005];
int n,mincost,tot;
void init()
{
	int d,w,i;
	dist[1]=0,wt[0]=0,swt[1]=0;
	scanf("%d%d",&wt[1],&dist[2]);
	tot=wt[1]*dist[2];
	for(i=2;i<=n;i++)
	{
		scanf("%d%d",&w,&d);
		wt[i]=wt[i-1]+w;
		dist[i+1]=dist[i]+d;
		swt[i]=swt[i-1]+w*dist[i];
		tot=tot+wt[i]*d;
	}
}
int getcost(int i,int j)
{
	if(i>j) return 0;
	else return tot-wt[i]*(dist[j]-dist[i])-wt[j]*(dist[n+1]-dist[j]);
}
int getw(int x,int y)
{
	if(x>y) return 0;
	else return ((wt[y-1]-wt[x])*dist[y]-(swt[y-1]-swt[x]));
}
/*int main()
{
	int i,j,k=0,temp;;
	while(scanf("%d",&n)!=EOF)
	{
		init();
		for(i=1;i<=n;i++) mincost[i][0]=getw(0,i+1);
		for(i=2;i<=n;i++)
		{
			for(j=1;j<=2;j++)
			{
				if(j>=i)mincost[i][j]=0;
				else
				{
			        mincost[i][j]=getw(1,i+1);
			        for(k=2;k<=i;k++)
			        {
				        temp=mincost[k-1][j-1]+getw(k,i+1);
				        if(temp<mincost[i][j])mincost[i][j]=temp;
			        }
				}
			}
		}
		printf("%d\n",mincost[n][2]);
	}

	return 0;
}*/
void comp(int minp1,int maxp1,int minp2,int maxp2)
{
	int i,j,cost,opt=0,optcost;
	if(minp1>=minp2) minp2=minp1+1;
	if(maxp1>=maxp2) maxp1=maxp2-1;
	if((minp1>maxp1)||(minp2>maxp2)) return;
	optcost=INT_MAX;
	j=(minp2+maxp2)/2;
	for(i=minp1;i<=min(maxp1,j-1);i++)
	{
		cost=getcost(i,j);
		if(cost<optcost)
		{
			opt=i;
			optcost=cost;
		}
	}
	if(optcost<mincost)mincost=optcost;
	comp(minp1,opt,minp2,(minp2+maxp2)/2-1);
	comp(opt,maxp1,(minp2+maxp2)/2+1,maxp2);
}
int main()
{
    int i,j,k=0,temp;;
	while(scanf("%d",&n)!=EOF)
	{
		init();
		mincost=INT_MAX;
		comp(1,n-1,2,n);
		printf("%d\n",mincost);
	}
	return 0;
}

参考答案(时间最优[68]):

#include<iostream>
#include<stdio.h>
#include<limits.h>
using namespace std;
int dist[20005],swt[20005],wt[20005];
int n,mincost,tot;
void init()
{
	int d,w,i;
	dist[1]=0,wt[0]=0,swt[1]=0;
	scanf("%d%d",&wt[1],&dist[2]);
	tot=wt[1]*dist[2];
	for(i=2;i<=n;i++)
	{
		scanf("%d%d",&w,&d);
		wt[i]=wt[i-1]+w;
		dist[i+1]=dist[i]+d;
		swt[i]=swt[i-1]+w*dist[i];
		tot=tot+wt[i]*d;
	}
}
int getcost(int i,int j)
{
	if(i>j) return 0;
	else return tot-wt[i]*(dist[j]-dist[i])-wt[j]*(dist[n+1]-dist[j]);
}
int getw(int x,int y)
{
	if(x>y) return 0;
	else return ((wt[y-1]-wt[x])*dist[y]-(swt[y-1]-swt[x]));
}
/*int main()
{
	int i,j,k=0,temp;;
	while(scanf("%d",&n)!=EOF)
	{
		init();
		for(i=1;i<=n;i++) mincost[i][0]=getw(0,i+1);
		for(i=2;i<=n;i++)
		{
			for(j=1;j<=2;j++)
			{
				if(j>=i)mincost[i][j]=0;
				else
				{
			        mincost[i][j]=getw(1,i+1);
			        for(k=2;k<=i;k++)
			        {
				        temp=mincost[k-1][j-1]+getw(k,i+1);
				        if(temp<mincost[i][j])mincost[i][j]=temp;
			        }
				}
			}
		}
		printf("%d\n",mincost[n][2]);
	}

	return 0;
}*/
void comp(int minp1,int maxp1,int minp2,int maxp2)
{
	int i,j,cost,opt=0,optcost;
	if(minp1>=minp2) minp2=minp1+1;
	if(maxp1>=maxp2) maxp1=maxp2-1;
	if((minp1>maxp1)||(minp2>maxp2)) return;
	optcost=INT_MAX;
	j=(minp2+maxp2)/2;
	for(i=minp1;i<=min(maxp1,j-1);i++)
	{
		cost=getcost(i,j);
		if(cost<optcost)
		{
			opt=i;
			optcost=cost;
		}
	}
	if(optcost<mincost)mincost=optcost;
	comp(minp1,opt,minp2,(minp2+maxp2)/2-1);
	comp(opt,maxp1,(minp2+maxp2)/2+1,maxp2);
}
int main()
{
    int i,j,k=0,temp;;
	while(scanf("%d",&n)!=EOF)
	{
		init();
		mincost=INT_MAX;
		comp(1,n-1,2,n);
		printf("%d\n",mincost);
	}
	return 0;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注