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; } };