SRM418 div2 hard

メモ化再帰すればいい。
だけど、
rec(m,b,o)でm=oかつm=unitsPerRoundな状態になると無限ループするので、途中で中断するように

if(r==-3)
	return r=(1<<28);
r--;

を入れておいた。

#include <algorithm>
#include <cstring>

using namespace std;

class BarracksEasy
{
	public:

		int unitsPerRound;
		int cache[50+1][50+1][100];

		int rec(int myUnits,int barHp,int opponentsUnits)
		{	
			//printf("myUnits=%d barHp=%d opponentsUnits=%d\n",myUnits,barHp,opponentsUnits);
		
			if(barHp==0 && opponentsUnits==0)
				return 0;
			if(myUnits==0)
				return (1<<28);
			
			int &r=cache[myUnits][barHp][opponentsUnits];
			if(0<r)
				return r;
			if(r==-3)
				return r=(1<<28);
			r--;
			int tmp=(1<<28);

			for(int killer=0;killer<=myUnits;killer++)
			{
				int breaker=myUnits-killer;
				
				int leftOpponentsUnits=max(0,opponentsUnits-killer);
				int leftOpponentHp=max(0,barHp-breaker);
				
				int leftMyUnits=max(0,myUnits-leftOpponentsUnits);
				leftOpponentsUnits+=(leftOpponentHp!=0)?unitsPerRound:0;
				
				tmp=min(tmp,1+rec(leftMyUnits,leftOpponentHp,leftOpponentsUnits));
			}
			return r=tmp;
		}

		int attack(int myUnits, int barHp, int _unitsPerRound)
		{
			unitsPerRound=_unitsPerRound;
			memset(cache,0,sizeof(cache));
			int ans=rec(myUnits,barHp,0);

			return ((1<<28)<=ans)?-1:ans;
		}
};

これでdiv2hard100耐は終了した