kthline.cpp

有向直线Ｋ中值问题 给定一条有向直线L以及L 上的n+1 个点x0<x1<x2<… <xn。有向直线L 上的每个点xi都有一个权 w(xi) 每条有向边 (xi,xi-1)

#include<math.h>
#include<string.h>
#include<stdio.h>
#include<iostream.h>
#include<fstream.h>
#include<time.h>

void Distance(int n,int *w,int **d,int **m)//计算出i,j之间的距离以及j转移到i的费用
{

    for(int i=0;i<=n;i++)
	{
		d[i][i]=0;
		m[i][i]=0;
	}
	for(i=0;i<n;i++)
		for(int j=i+1;j<=n;j++)
		{
           d[j][i]=d[j-1][i]+d[j][j-1];
		   m[j][i]=w[j]*d[j][i];
		}
}

int c(int i,int n,int k,int *w,int **d,int **m)
{
	int s=0,t=0,j;//s用来计算最优的费用，t用来纪录总费用
	if(k==1) 
	{
		for(j=n;j>i;j--)
			t+=m[j][i];
		return t;
	}
	if(i==n-k+1) return 0;
	for(j=n-k+1;j>i;j--)//计算后面一段都是服务站的总费用
		s+=m[j][i];
	for(j=n-k+1;j>i;j--)
	{
		t=0;
		for(int r=j-1;r>i;r--)
		{
			t+=m[r][i];
		}
		t+=c(j,n,k-1,w,d,m);
		if(t<s)
		{
			s=t;
		}
	}
	return s;
}

void main()
{

	int n,k,t=0;//n站点数，K是增设服务站数，t用来记录服务总费用
	ifstream input("input.txt");
	ofstream output("output.txt");
	int *w,**d,**m;
	input>>n;
	input>>k;
	w=new int[n+1];//w数组用来记录权值
    d=new int* [n+1];//d用来记录两点之间的距离
	for(int i=0;i<=n;i++)
		d[i]=new int[n+1];
	m=new int* [n+1];//m用来记录两点之间的转移费用
	for( i=0;i<=n;i++)
		m[i]=new int[n+1];
	for(i=n;i>0;i--)
	{
		input>>w[i];
		input>>d[i][i-1];
	}

    Distance(n,w,d,m);
	t=c(0,n,k+1,w,d,m);

	output<<t<<endl;

    delete []w;
	for(i=0;i<=n;i++)
		delete []d[i];
	for(i=0;i<=n;i++)
		delete []m[i];

}