某島

… : "…アッカリ～ン . .. . " .. .
June 20, 2014

500. BlockTheBlockPuzzle

… 略）

Analysis:

    int minimumHoles(vector <string> board) {
r = board.size (), c = board[0].size (); init();

REP_2(i, j, r, c) if (board[i][j] == 'b'){
add_edge(V(i, j), V(i, j, 1), INF);
}
else if (board[i][j] == '\$'){
t = V(i, j, 1); add_edge(V(i, j), V(i, j, 1), INF);
board[i][j] = 'b';
}
else if (board[i][j] == '.'){
add_edge(V(i, j), V(i, j, 1), 1);
}

REP_2(i, j, r, c){
if (j+3 < c){
int cc = (board[i][j+1] == 'b') || (board[i][j+2] == 'b') ? INF : (board[i][j+1] == '.') + (board[i][j+2] == '.');
add_edge(V(i, j, 1), V(i, j+3), cc);
add_edge(V(i, j+3, 1), V(i, j), cc);
}
if (i+3 < r){
int cc = (board[i+1][j] == 'b') || (board[i+2][j] == 'b') ? INF : (board[i+1][j] == '.') + (board[i+2][j] == '.');
add_edge(V(i, j, 1), V(i+3, j), cc);
add_edge(V(i+3, j, 1), V(i, j), cc);
}
}

return Dinitz();
}


900. Seatfriends

Analysis:

。。。dp[i][j] 表示 i 個人、 j 個 cluster 時的方案數。。。
。。主要就是搞兩次。dp 時。不要去處理 cluster 間具體有多少空格的問題。。
。再往之間插入空格就行了。。。

const int N = 2009;
Int dp[2][N], Binom[N][N];

class Seatfriends {
public:
int countseatnumb(int n, int m, int g) {

REP(i, N){Binom[i][0] = 1; REP_1(j, i) Binom[i][j] = Binom[i-1][j-1] + Binom[i-1][j];}

#define u dp[q][j]
#define v dp[p]

int p = 0, q = 1; RST(dp[p]); dp[p][1] = n;

FOR(i, 1, m){
swap(p, q); RST(dp[p]);
REP_1(j, g) if (u){
v[j] += u*j*2;
v[j+1] += u*j;
v[j-1] += u*j;
}
}

if (n == m) return dp[p][0];
Int res = 0; REP_1(i, g) res += dp[p][i] * Binom[n-m-1][i-1];
return res;
}
};