SRM513 Div2 Hard(1000) CutTheNumbers

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