有向直线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;
}题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。