m处理器问题.cpp

动态规划解一系列经典问题

#include<iostream.h>
#include<fstream.h>
#include<math.h>

double s[6][3];
double f(int *e,int i,int j)
{
	double result=0;
	for(int k=i;k<=j;k++)result+=e[k];
	return sqrt(result);
}

double alloc(int *e,int m,int n)
{
	int k;
	for(int i=n-1;i>=0;i--)s[i][0]=f(e,i,n-1);
	for(i=1;i<m;i++){
		s[n-i][i]=f(e,n-i,n-i)>s[n-i+1][i-1] ? f(e,n-i,n-i) : s[n-i+1][i-1];
		k=n-i;
		for(int j=n-i-1;j>=m-i-1;j--){
			if(f(e,j,k)<=s[k+1][i-1])s[j][i]=f(e,j,k);
			else
				if(f(e,j,j)>=s[j+1][i-1])s[j][i]=f(e,j,j);
				else{
					while(f(e,j,k-1)>=s[k][i-1])k--;
					s[j][i]=f(e,j,k)>s[k][i-1] ? f(e,j,k) : s[k][i-1];
					if(s[j][i]==s[k][i-1])k--;
				}
		}
	}
	return s[0][m-1];
}


void main()
{
	int n;
	int m;
	int v;
	//int **s;
	ifstream infile("input.txt");
	if(!infile){
		cout<<"Can't open input.txt!"<<'\n';
		return;
	}
	
	ofstream outfile("output.txt");
	if(!outfile){
		cout<<"Can't open output.txt!"<<'\n';
		return;
	}
	cout<<"Please input data into file \"input.txt\"";
	infile>>n;
	infile>>m;
	int *e=new int[n];
	for(int i=0;i<n;i++){
		infile>>e[i]; 
		v=e[i]*e[i];
		e[i]=v;
	}
	outfile<<alloc(e,m,n)<<endl;
	cout<<alloc(e,m,n)<<endl;
	delete []e;
	
	infile.close();
	outfile.close();
}