SRM370 div1medium

通信範囲を１づつ大きくしながらメモ化再帰。

#include <algorithm>
#include <vector>

using namespace std;

class ConnectTheCities 
{
	public:

		int n,dist,range;
		vector<int> pos;
		int cache[105][55];

		int rec(int bP,int k)
		{
			//printf("bP=%d k=%d\n",bP,k);

			int &r=cache[bP][k];
			if(r!=-1)
				;
			else if(k==n)
			{
				if(dist-range<=bP)
					r=0;
				else
					r=1000000;
			}
			else
			{
				r=1000000;
				for(int nP=bP;nP<=min(bP+range,dist);nP++)
					r=min(r,abs(nP-pos[k])+rec(nP,k+1));
			}
			return r;
		}		

		int minimalRange(int distance, int funds, vector <int> position) 
		{
			dist=distance;
			pos=position;
			sort(pos.begin(),pos.end());
			n=pos.size();
			pos.push_back(distance);

			//printf("n=%d\n",n);

			for(range=1;range<=distance;range++)
			{
				memset(cache,-1,sizeof(cache));
				if(rec(0,0)<=funds)
					return range;
			}
		}
};