Codeforces Round #102 (Div. 1) C : Help Caretaker
問題概要
T字型のペントミノをH*W(H,W<=9)に最大いくつ敷き詰められるか求める問題。実際に敷き詰めたものを出力する。
解法
2行覚えておくビットDPでもいけるけど復元がとても面倒。普通に探索する。分枝限定法で枝刈りできる。
また、この問題は最大独立集合だとみなすこともできる(ノード数9*9*4)。いつか最大独立集合ソルバができたら試してみたい。
acceptされたコード
#include <cstdio> #include <cstring> using namespace std; const int MAX_W = 15; const int dy[][5] = { {0,0,0,1,2}, {0,1,1,1,2}, {0,1,2,2,2}, {0,1,1,1,2}, }; const int dx[][5] = { {0,1,2,1,1}, {2,0,1,2,2}, {1,1,0,1,2}, {0,0,1,2,0}, }; int H, W; char board[MAX_W][MAX_W + 1]; char best_board[MAX_W][MAX_W + 1]; int best_score, res, cur; void init(){ scanf("%d%d", &H, &W); for(int i=0; i<H; i++){ for(int j=0; j<W; j++){ board[i][j] = best_board[i][j] = '.'; } } } inline bool can_put(int y, int x, int p){ for(int k=0; k<5; k++){ int ny = y + dy[p][k], nx = x + dx[p][k]; if( !(0<=ny && ny<H && 0<=nx && nx<W && board[ny][nx]=='.') ){ return false; } } return true; } inline void draw(int y, int x, int p, char col){ for(int k=0; k<5; k++){ int ny = y + dy[p][k], nx = x + dx[p][k]; board[ny][nx] = col; } } void rec(int y, int x){ if(x == W){ if(y < H){ rec(y+1, 0); } return ; } if(cur + res/5 <= best_score){ return ; } if(y <= H-3 && x <= W-3){ int tmp = res; for(int p=0; p<4; p++){ if(can_put(y, x, p)){ draw(y, x, p, 'A' + cur++); if(best_score < cur){ best_score = cur; memcpy(best_board, board, sizeof(board)); } res -= 5 + (board[y][x] == '.' ? 1 : 0); rec(y, x+1); res = tmp; cur--; draw(y, x, p, '.'); } } } if(board[y][x] == '.'){ res--; } rec(y, x+1); if(board[y][x] == '.'){ res++; } } void solve(){ cur = 0; res = H * W; rec(0, 0); printf("%d\n", best_score); for(int i=0; i<H; i++){ puts(best_board[i]); } } int main(){ init(); solve(); return 0; }