TopCoder SRM 513 Div2 Hard CutTheNumbers

なかなか面白い問題。
http://community.topcoder.com/stat?c=problem_statement&pm=11501

問題

最大4x4のグリッドの各セルに数字が書かれている。
各セルは隣接セル同士を連結し、幅１マスまたは高さ１マスの長方形とすることができる。
各長方形のスコアは、各セルの数字を上からまたは左から連結して生成できる数値となる。

グリッドに対して得られるスコアを最大値を求めよ。

解法

与えられるグリッドが4x4より小さい場合、左または上に0の書かれたセルをくっつけて4x4にしてしまおう。
これらのセルがあっても最終的なスコアに影響しない。

セルの数は高々16なので、各セルの使用未使用をbitmaskで持ってbitDPし、未使用セルを連結して得られる数値を加算して最大化していけばよい。

int mama[1<<16];
int type[1<<16];
class CutTheNumbers {
	public:
	vector<string> B;
	int maximumSum(vector <string> board) {
		int i,mask,x,y,nmask;
		B.clear();
		FOR(i,4) {
			string s="0000";
			if(i>=4-board.size()) s+=board[i-(4-board.size())];
			B.push_back(s.substr(s.size()-4));
		}
		MINUS(type);
		FOR(y,4) FOR(x,4) {
			int tm=1<<(y*4+x);
			type[tm]=B[y][x]-'0';
			for(int tx=x+1;tx<4;tx++) {
				tm |= 1<<(y*4+tx);
				type[tm]=type[tm^(1<<(y*4+tx))]*10+B[y][tx]-'0';
			}
			tm=1<<(y*4+x);
			for(int ty=y+1;ty<4;ty++) {
				tm |= 1<<(ty*4+x);
				type[tm]=type[tm^(1<<(ty*4+x))]*10+B[ty][x]-'0';
			}
		}
		vector<pair<int,int> > V;
		FOR(i,1<<16) if(type[i]>=0) V.push_back(make_pair(i,type[i]));
		
		
		ZERO(mama);
		FOR(mask,1<<16) FOR(i,V.size()) if((mask & V[i].first)==0) 
			mama[mask|V[i].first] = max(mama[mask|V[i].first],mama[mask]+V[i].second);
		return mama[0xFFFF];
	}
};

まとめ

２次元のグリッドに対するbitDPって珍しいな。