thline.cpp

有向直线2中值问题 对于给定的有向直线L

#include<iostream.h>
#include<fstream.h>
#include<time.h>
typedef unsigned long hh;

void main()
{
	clock_t start,finish;
	start=clock();
	ifstream infile("input.txt",ios::in);
	ofstream outfile("output.txt",ios::out);
	int n;
	infile>>n;
	int i=0,j=0;

	hh *a=new hh[n];
	hh *b=new hh[n];
	for(i=0;i<n;i++)
	{
		infile>>a[n-1-i];
		infile>>b[n-1-i];
	}

	hh **c=new hh*[n];
	hh **cost=new hh*[n];
	for(i=0;i<n;i++) 
	{
		c[i]=new hh[n];
		cost[i]=new hh[n];
	}
	int sum=0,v=0,p=0,s=0,u=0;
	for(i=0;i<n;i++)
		c[i][i]=b[i];
	for(i=0;i<n;i++)		//c[j][i]表示xj+1点到xi点的距离(j+1表示下标)
	{
		for(j=i+1;j<n;j++)
		{
			c[j][i]=c[j-1][i]+b[j];
		}
	
	}
	for(i=0;i<n;i++)
		cost[i][i]=a[i]*c[i][i];
	sum=0;
	for(i=0;i<n;i++)
	{
		for(j=i+1;j<n;j++)
		{
				cost[j][i]=cost[j-1][i]+a[j]*c[j][i];
		}
	}


	
	for(i=n;i>1;i--)//这里设xi和xj为两个最优点且(xi>xj)
	{	
		if(i<n)
		{
			sum=cost[n-1][i];	//算出xn到xi的服务量
		}
		else
		{
			sum=0;
			u=cost[n-3][0];
		}
		if(i>3)		//求出xi到x0的服务量最小值，并留下记号
		{	
			v=cost[i-3][0];   //设一初值，用于比较，v最后的结果是xi到x0的服务量最小值	
			for(j=i-2;j>0;j--)
			{
				p=cost[i-2][j];				//xi到xj的服务量
				if(j>1)
				{
					s=cost[j-2][0];		//xj到x0的服务量
				}
				else
					s=0;
				if(p+s<v)
				{
					v=p+s;
				}
			}
		}
		else
			v=0;
		if(sum+v<u)
			u=sum+v;
	}
	outfile<<u;
	delete []a;
	delete []b;
	delete []c;
	delete []cost;
	finish=clock();
	cout<<finish-start<<endl;
}