SRM513 Div2 Hard(1000) CutTheNumbers
メモ化探索。板のサイズが小さいので、板の切り取りかた全てについて、最大の和を覚えておくことができる。
#include <string> #include <vector> using namespace std; int memo[1<<16]; int bit( int x, int y ) { return 1<<(y*4+x); } int BT( vector<string> board, int used ) { if ( memo[used] >= 0 ) return memo[used]; int h = (int)board.size(); int w = (int)board[0].size(); int ox=-1, oy=-1; for ( int y=0; y<h && oy==-1; y++ ) for ( int x=0; x<w && ox==-1; x++ ) if ( !(used&bit(x,y)) ) ox = x, oy = y; if ( ox == -1 ) return memo[used] = 0; int ans = 0; // 横 int u = used; int t = 0; for ( int i=0; ox+i<w && !(used&bit(ox+i,oy)); i++ ) { t = t*10 + (board[oy][ox+i]-'0'); u |= bit(ox+i,oy); ans = max( ans, t+BT(board,u) ); } // 縦 u = used; t = 0; for ( int i=0; oy+i<h && !(used&bit(ox,oy+i)); i++ ) { t = t*10 + (board[oy+i][ox]-'0'); u |= bit(ox,oy+i); ans = max( ans, t+BT(board,u) ); } return memo[used] = ans; } class CutTheNumbers{public: int maximumSum( vector <string> board ) { for ( int i=0; i<1<<16; i++) memo[i] = -1; return BT( board, 0 ); }};