dynscheme.cpp

奥运指示牌的放置问题：海淀区某广告公司负责为到京观看奥运比赛的群众设置指示 牌

#include "DynScheme.h"
#include <iostream>
using namespace std;
DynScheme::DynScheme(void)
{
}

DynScheme::~DynScheme(void)
{
}

DynScheme::DynScheme(int xx[],int rr[],int ele):x(xx,xx+ele),r(rr,rr+ele)
{
	memset(matrix,-1,20*5*sizeof(int));
}
int DynScheme::Scheme(int first,int last,int cur)
{
	int result = 0;
	int pos = 0;
	int max = 0;

	//if( matrix[first][cur] >= 0 )
	//{
	//	cout<<"value used! "<<matrix[first][cur]<<endl;

	//	if( matrix[first][cur] > 0 )
	//		xx.push_back(pos);                    //bug!!!!!!!!!!!!!!!!!这里的pos必须是max( cur,last cur)!!!!!

	//	return matrix[first][cur];
	//}
	if(last - first <= 5)
	{
		//return max( r[first,last] )
		for(int i = cur; i < r.size(); i++)
		{
			if( r[i] > result)
			{
				result = r[i];
				pos = i;
			}
		}
		if( result > 0 )
		{	
			xx.push_back(pos);
		}
		//填表！
		/*matrix[ x[pos] ][cur] = result;*/
		return result;
	}
	else
	{
		//在first到first+5的范围内，求cur,满足：[oldcur,newcur)之间的first<x[i]<first+5
		int newcur = cur;
		while(( newcur < x.size() )&&( x[newcur] <= first+5 ))
			newcur++;//如果循环结束，则newcur为所求

		if( newcur == cur)//first到first+5的范围内没有广告牌
		{
			result += Scheme(first+5,last,newcur);//result = 0 + Scheme(first+5,last,newcur)
			/*if( matrix[ first+5 ][ cur ] >= 0 )
				cout<<"value changed! :"<<matrix[ first+5 ][ cur ]<<" to "<<result<<endl;
			matrix[ first+5 ][ cur ] = result;*/
		}
		else
		{
			for(int i = cur; i < newcur; i++)
			{
				//return max( x[i]+Scheme(first+5,last) );
				max = r[i] + Scheme( x[i],last,nextcur(i) );

				/*if( matrix[ first+5 ][ cur ] >= 0 )
					cout<<"value changed! :"<<matrix[ x[i] ][ cur ]<<" to "<<max<<endl;

				matrix[ x[i] ][ cur ] = max;*/
				if(result < max)
				{
					result = max;//result保留最大值
					pos = i;//pos 保留最大值的位置
				}
			}
			xx.push_back(pos);
		}
		return result;
	}
}
int DynScheme::nextcur(int i)
{
	int y = i + 1;
	while(( y < x.size() )&&( x[y] <= x[i]+5 ))
		y++;
	return y;
}