apply.cpp

货郎担问题！这是用动态规划实现的！ 效率很高啊！

#include"iostream.h"
#include"fstream.h"
#include"stdlib.h"
#include"math.h"
#include "iomanip.h"
#include"time.h"
int partion(double **a,int low,int high)
	{
	double key=a[low][0];
	double key1=a[low][1];
    while(low<high)
	{
		while(low<high&&a[high][0]>=key)
			--high;
		  a[low][0]=a[high][0];
		  a[low][1]=a[high][1];
		 while(low<high&&a[low][0]<=key)
			++low;
		 a[high][0]=a[low][0];
		 a[high][1]=a[low][1];
	}
	a[low][0]=key;
	a[low][1]=key1;
   return low;
	}
void qsort(double **a,int low,int high)
{
	if(low<high)
	{
		int p=partion(a,low,high);
		qsort(a,low,p-1);
		qsort(a,p+1,high);
	}
}
double digui(int i,double *min,double **d,double **b)
{
	if (d[i]!=-1) return min[i];
	if (i==n) return d[n-1][n];
	double temp=b[i][i]+digui(i+1,min,d,b)+d[i-1][i+1];//i==j;
	for(int k=i+1;k<=n-1;k++)
	{
		double temp1=b[i][k]+digui(k+1,min,d,b)+d[i-1][k+1];
		if (temp>temp1) temp=temp1;
	}
	min[i]=temp;
	return temp;
}
void main()
{
	ifstream in("input.txt");
	if(!in)
	{
		cerr<<"can't open input file\n";
		exit(0);
	}
	int n;
	in>>n;
	double **a=new double *[n+1];
	double **b=new double *[n+1];
	double **d=new double *[n+1];
	double *min=new double[n+1];
	for(int i=0;i<n;i++)
	{
		a[i]=new double[2];
		b[i]=new double[n+1];
		d[i]=new double[n+1];
		in>>a[i][0];
	//	cout<<a[i][0]<<";";
		in>>a[i][1];
		min[i]=-1;
	//	cout<<a[i][1];
	//  out<<endl;
	}
	qsort(a,0,n-1);
	 for(int i=1;i<=n;i++)
    for(int j=i;j<=n;j++)
	{
		d[i][j]=sqrt(pow((a[i][0]-a[j][0]),2)+pow((a[i][1]-a[j][1]),2));
	}
	for(i=1;i<=n;i++)
		for(j=i;j<=n;j++)
			{ 
			double sum=0;
	        for(int k=i;k<=j-1;k++)	
				sum+=d[k][k+1];
                b[i][j]=sum;
		}
	 digui(1,min,d,b);
     ofstream out("output.txt");//建立并打开输出文件
	if(!out)
	{
		cerr<<"can't open output file.\n";
		exit(1);
	}
	//double t;
//	t=clock();
	out<<setiosflags(ios::fixed)<<setprecision(2)<<d[1]<<endl;
//	out<<t;
    out.close();
    in.close();
    delete[]a;
    delete[]b;
 }