500. BlockTheBlockPuzzle
Brief description:
… 略）
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(s, V(i, j, 1), INF);
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
Brief description:
略。）
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;
}
};
