SRM351 div1 medium

rec(直前の色、直前の色は何個続いたか、Aの個数、Bの個数、Cの個数)をメモ化再帰
場所は全体の長さ-(Aの個数+Bの個数+Cの個数)で求められる。

#include <algorithm>
#include <vector>

using namespace std;

int cache[3][4][50+10][50+10][50+10];

class BoxesArrangement 
{
	public:

		int len;
		string boxes;

		int rec(int w,int n,int A,int B,int C)
		{
			int p=len-A-B-C;
			int &r=cache[w][n][A][B][C];

			if(r!=-1000)
				return r;
			else if(n==3)
				r=-100;
			else if(p==len)
				r=0;
			else
			{
				r=-100;
				if(0<A)
				{
					int nn=(w==0)?n+1:1;
					int t=(boxes[p]=='A')?1:0;
					r=max(r,rec(0,nn,A-1,B,C)+t);
				}
				if(0<B)
				{
					int nn=(w==1)?n+1:1;
					int t=(boxes[p]=='B')?1:0;
					r=max(r,rec(1,nn,A,B-1,C)+t);
				}
				if(0<C)
				{
					int nn=(w==2)?n+1:1;
					int t=(boxes[p]=='C')?1:0;
					r=max(r,rec(2,nn,A,B,C-1)+t);
				}
			}

			return r;
		}

		int maxUntouched(string _boxes) 
		{
			boxes=_boxes;
			len=boxes.size();
			int A=0,B=0,C=0;
			for(int i=0;i<boxes.size();i++)
				if(boxes[i]=='A')
					A++;
				else if(boxes[i]=='B')
					B++;
				else
					C++;

			cout << endl;

			fill(&cache[0][0][0][0][0],&cache[2][3][59][59][59],-1000);
			int ans=rec(0,0,A,B,C);

			return (ans<0)?-1:ans;
		}
};